Leetcode 【39、40、77】

问题描述：【DFS、DP】39. Combination Sum

解题思路：

这道题和 Leetcode 【DP】518. Coin Change 2 是一样的，只不过这道题要输出所有的组合数，而 Leetcode 518 是输出组合数的次数。

方法1（DFS）：

第一种方法，容易想到用 DFS 回溯法求解，candidates 中的数字为算符种类数。每次深搜时，更新当前 target，当 target 为 0 时 输出结果。

Python3 实现：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def search(tar):
            for c in candidates:
                if a[-1] <= c:  # 组合数
                    a.append(c)
                    tar -= c
                    if tar == 0:
                        ans.append([])
                        for n in a:
                            ans[-1].append(n)
                        ans[-1].pop(0)  # 把前面的一个0去掉
                    elif tar > 0:
                        search(tar)
                    a.pop()  # 恢复，回溯一步
                    tar += c  # 恢复，回溯一步
                        
        ans = []
        a = [0] # 防止下标越界
        search(target)
        return ans

方法2（DP）：

因为 Leetcode 【DP】518. Coin Change 2 是使用动态规划的思路求解的，只不过 dp[i] 中存储的是组合数的次数。如果我们将 dp[i] 中存储的次数改为存储的当前结果，就可以使用 DP 方法来求解这道题。

举个例子，比如 candidates = [1, 2]，target = 2；

• 初始化时 dp[0] = [[]]，便于后续的 dp[i] 中结果的生成；
• 用 c = 1 时，dp[1] = [[1]]，dp[2] = [[1,1]]；
• 用 c = 2 时，比如要将 dp[2] 更新为 [[1,1], [2]]，则 dp[i] 依赖于 dp[i-c] 中的每一项 item，然后把 item + [c] 压入 dp[i] 中，就实现了更新的目的。

Python3 实现：

class Solution:
    def combinationSum(self, candidates, target: int):
        dp = [[] for _ in range(target+1)]
        dp[0].append([])
        for c in candidates:
            for i in range(c, target+1):
                for item in dp[i-c]:
                    dp[i].append(item+[c])
        return dp[-1]

---

问题描述：【DFS】40. Combination Sum II

解题思路：

方法同 Leetcode 39，只不过 candidates 中可能有重复的数字，因此可能构造出重复的结果。比如，candidates = [1,2,1]，target = 3，会出现两次 [1,2]。因此，找到一组解后，还要判断之前是否已经出现过，如果出现过，就不加进去。

Python3 实现：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def search(tar):
            for k, v in enumerate(candidates):
                if not b[k] and a[-1] <= v:
                    a.append(v)
                    b[k] = True
                    tar -= v
                    if tar == 0:
                        tem = []
                        for n in a:
                            tem.append(n)
                        tem.pop(0)
                        if tem not in ans:  # 去重
                            ans.append(tem)
                    elif tar > 0:
                        search(tar)
                    a.pop()
                    b[k] = False
                    tar += v     
        
        a = [0]
        b = [False] * len(candidates)
        ans = []
        search(target)
        return ans

---

题目描述：【DFS】77. Combinations

解题思路：

求解 C(n, r) 的问题，使用 DFS 回溯法求解即可。

Python3 实现：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def search(ind, r, path):  # ind代表遍历的索引，防止找出的是排列数
            for i in range(ind, n+1):
                path += [i]
                if r == k:
                    ans.append(path[:])  # 注意这里传引用调用，不然path变化ans也会改变
                else:
                    search(i+1, r+1, path)
                path.pop()
                
        ans = []
        search(1, 1, [])
        return ans