问答

当前位置

组合求和

  • Ta: 李玉哲

请问这题中
class Solution: candidates = sorted(list(set(candidates))) set 的作用是什么
还有这样的题目时间复杂度怎么求解
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
candidates = sorted(list(set(candidates)))
results = []
self.dfs(candidates, target, 0, [], results)
return results

# 递归的定义:在candidates[start ... n-1] 中找到所有的组合,他们的和为 target
# 和前半部分的 combination 拼起来放到 results 里
# (找到所有以 combination 开头的满足条件的组合,放到 results)
def dfs(self, candidates, target, start, combination, results):
    # 递归的出口:target <= 0
    if target < 0:
        return

    if target == 0:
        # deepcooy
        return results.append(list(combination))

    # 递归的拆解:挑一个数放到 combination 里
    for i in range(start, len(candidates)):
        # [2] => [2,2]
        combination.append(candidates[i])
        self.dfs(candidates, target - candidates[i], i, combination, results)
        # [2,2] => [2]
        combination.pop()  # backtracking

1 个回复

2019-09-11 carry

这个算法的实质就是遍历了所有的组合,所以最坏情况下要检查所有的子集,时间复杂度是O(2 ^ n)

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1