dfs+剪枝，LeetCode 39. 组合总和

一、题目

1、题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

2、接口描述

python3

​

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

cpp

​

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
    }
};

3、原题链接

39. 组合总和

---

二、解题报告

1、思路分析

考虑暴力dfs，选多个或不选，当前枚举到 i ，还差res数值

            
            dfs(i - 1, res)
 
            path.append(candidates[i])
            dfs(i, res - candidates[i])
            path.pop()

显然可以剪枝，res 小于0的时候剪掉（可行性剪枝）

进一步，我们优化搜索顺序，从小到大枚举

当res < candidate[i]时，往后枚举不能满足，也可以剪枝（优化搜索顺序剪枝）

这样这道题其实就蛮快了

但是如果数据量更大呢？

搜索树的起点终点已知，可以双向广搜，能够有效降低复杂度

但是我们发现每个结点都相当于一个完全背包的状态

换言之，我们预处理完全背包，就可以使得搜索顺序朝着可行路径去走

所以采用预排序和预处理完全背包来进行剪枝：

优化搜索顺序 & 可行性剪枝

2、复杂度

时间复杂度： 不会算 空间复杂度：O(n target)

3、代码详解

python3

​

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        candidates.sort()
        f = [[False] * (target + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(candidates):
            for j in range(target + 1):
                f[i + 1][j] = f[i][j] or j >= x and f[i + 1][j - x]
        
        ret = []
        path = []
        def dfs(i: int, res: int):
            if not res:
                ret.append(path.copy())
                return
            
            if res < 0 or not f[i + 1][res]:
                return
            
            dfs(i - 1, res)
 
            path.append(candidates[i])
            dfs(i, res - candidates[i])
            path.pop()
 
        dfs(n - 1, target)
 
        return ret

cpp

​

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> path;
        int n = candidates.size();
        sort(candidates.begin(), candidates.end());
        vector<vector<bool>> f(n + 1, vector<bool>(target + 1));
        f[0][0] = 1;
        for(int i = 0; i < n; i++)
            for(int j = 0; j <= target; j++)
                f[i + 1][j] = f[i][j] || (j >= candidates[i] && f[i + 1][j - candidates[i]]);
        function<void(int, int)> dfs = [&](int i, int res){
            if(!res) {
                ret.emplace_back(path);
                return;
            }
            if(res < 0 || !f[i + 1][res]) return;
            dfs(i - 1, res);
 
            path.emplace_back(candidates[i]);
            dfs(i, res - candidates[i]);
            path.pop_back();
        };
        dfs(n - 1, target);
        return ret;
    }
};