Leetcode 39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解析：
给定一组无重复的候选数据集和一个目标值，从候选数据集中找到所有的和为目标值的数字，数字可以重复不限制次数。
具体可以看题目中给出的示例。
题目要求给出所有的组合，当不好确定明显的动态规划或者递推关系时，可以考虑采用回溯算法。采用深度优先遍历，尝试将当前元素加入，递归确定是否满足条件，然后删除回溯。同时记录当前元素的下标值，为了防止重复组合，当前元素之前的元素不必再遍历。
具体来说：
设置起始下标start，记录当前处理元素的下标，设置sum记录当前加入的所有元素之和，同时记录目标值，从start=0,sum=0开始，尝试将当前元素加入，同时sum增加，采用递归方式判断是否是一个可行解，当sum==target时即为找到一组可行解，当sum>target时不符合题意，剪枝返回，通过深度优先遍历找到一组可行解，然后将当前元素删除进行回溯操作，继续寻找下一个元素。
代码如下：

class Solution {
public:
    vector<vector<int>>res;//记录所有结果组合
    vector<int>ans;//记录一组可行解
    int nums_len;

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        if(candidates.empty()) 
            return res;
        nums_len = candidates.size();
        dfs(0, 0, target, candidates);
        return res;
    }

    void dfs(int start, int sum, int target,vector<int>& candidates){//深度优先遍历算法
        if(sum == target) //找到一组目标值
        {
            res.push_back(ans); 
            return; 
        }
        else if(sum > target)//不符合条件，剪枝返回
            return;
        else{
            for(int i = start; i < nums_len; i++){//从当前下标一直遍历到结尾
                ans.push_back(candidates[i]);//将当前元素加入
                dfs(i, sum + candidates[i], target, candidates);//深度遍历，在加入当前元素基础上尝试找到一组解
                ans.pop_back();//回溯
            }
        }
    }

};

运行结果如下：
回溯法中，首先需要明确下面三个概念：

1.约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。

2.状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。

3.扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
在回溯法中，一般都用DFS。可以通过约束函数杀死一些节点从而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。FIFO 理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。

回溯法可以被认为是一个有过剪枝的DFS过程，利用回溯法解题的具体步骤。
首先，要通过读题完成下面三个步骤：
(1) 描述解的形式，定义一个解空间，它包含问题的所有解。
(2) 构造状态空间树。
(3) 构造约束函数（用于杀死节点）。

然后就要通过DFS思想完成回溯，完整过程如下：
(1) 设置初始化的方案（给变量赋初值，读入已知数据等）。
(2) 变换方式去试探，若全部试完则转(7)。
(3) 判断此法是否成功（通过约束函数），不成功则转(2)。
(4) 试探成功则前进一步再试探。
(5) 正确方案还未找到则转(2)。
(6) 已找到一种方案则记录并打印。
(7) 退回一步（回溯），若未退到头则转(2)。
(8) 已退到头则结束或打印无解。
参考：
https://blog.csdn.net/c602273091/article/details/54799621