稀碎从零算法笔记Day54-LeetCode:39. 组合总和

题型：数组、树、DFS、回溯

链接：39. 组合总和 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

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

题目样例

示例 1：

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

题目思路

乍一看这题目很像用DP来统计组合次数，直到看道函数返回的是二维数组，才意识到问题

但还是继续走DP这条路，最后发现如果是二维DP[i][j]的话，最后返回的答案是个一维数组……

看题解发现应该用【回溯】来处理：将2加入后，如果sum<target就继续加，直到sum>=target。
>的话说明这条路径不行，那就换一条路径；==的话就可以添加到ans中。
路径不行，就需要【回溯】到刚才——那就把sum(sum-=)还原回去，把path更新(pop_back)回去。

有个n叉树的深度优先(n是数字的个数)

C++代码

class Solution {
    // 回溯 树的深度优先相当于
    vector<int> path;
    vector<vector<int>> ans;
    void backAgain(vector<int> &candidates,int target,int sum,int start){
        //  回溯结束条件:
        if(sum > target) return;
        if(sum == target){
            ans.push_back(path);
            return;
        }
        for(int i=start;i<candidates.size();++i){
            sum += candidates[i];
            path.push_back(candidates[i]);
            //实现之前当过前缀的数 后面不会再出现
            backAgain(candidates,target,sum,i);
            // 如果执行到这一步 说明这条路径不符合
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ans.clear();
        path.clear();
        backAgain(candidates,target,0,0);
        return ans;
    }
};