問題描述：【DFS、DP】39. Combination Sum

解題思路：

這道題和 Leetcode 【DP】518. Coin Change 2 是一樣的，只不過這道題要輸出所有的組合數(shù)，而 Leetcode 518 是輸出組合數(shù)的次數(shù)。

方法1（DFS）：

第一種方法，容易想到用 DFS 回溯法求解，candidates 中的數(shù)字為算符種類數(shù)。每次深搜時，更新當(dāng)前 target，當(dāng) target 為 0 時 輸出結(jié)果。

Python3 實(shí)現(xiàn)：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def search(tar):
            for c in candidates:
                if a[-1] <= c:  # 組合數(shù)
                    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()  # 恢復(fù)，回溯一步
                    tar += c  # 恢復(fù)，回溯一步
                        
        ans = []
        a = [0] # 防止下標(biāo)越界
        search(target)
        return ans

方法2（DP）：

因?yàn)?Leetcode 【DP】518. Coin Change 2 是使用動態(tài)規(guī)劃的思路求解的，只不過 dp[i] 中存儲的是組合數(shù)的次數(shù)。如果我們將 dp[i] 中存儲的次數(shù)改為存儲的當(dāng)前結(jié)果，就可以使用 DP 方法來求解這道題。

舉個例子，比如 candidates = [1, 2]，target = 2；

• 初始化時 dp[0] = [[]]，便于后續(xù)的 dp[i] 中結(jié)果的生成；
• 用 c = 1 時，dp[1] = [[1]]，dp[2] = [[1,1]]；
• 用 c = 2 時，比如要將 dp[2] 更新為 [[1,1], [2]]，則 dp[i] 依賴于 dp[i-c] 中的每一項(xiàng) item，然后把 item + [c] 壓入 dp[i] 中，就實(shí)現(xiàn)了更新的目的。

Python3 實(shí)現(xiàn)：

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 中可能有重復(fù)的數(shù)字，因此可能構(gòu)造出重復(fù)的結(jié)果。比如，candidates = [1,2,1]，target = 3，會出現(xiàn)兩次 [1,2]。因此，找到一組解后，還要判斷之前是否已經(jīng)出現(xiàn)過，如果出現(xiàn)過，就不加進(jìn)去。

Python3 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def search(ind, r, path):  # ind代表遍歷的索引，防止找出的是排列數(shù)
            for i in range(ind, n+1):
                path += [i]
                if r == k:
                    ans.append(path[:])  # 注意這里傳引用調(diào)用，不然path變化ans也會改變
                else:
                    search(i+1, r+1, path)
                path.pop()
                
        ans = []
        search(1, 1, [])
        return ans