Leetcode 39. 组合总和 dfs

地址 https://leetcode-cn.com/problems/combination-sum/

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
 

提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

解法
DFS 暴力遍历
根据题目意义 所有元素独一无二
数据量偏小
对于一个包含不同元素的集合 {A,B,C,D}
我们对于每个元素逐个尝试
比如
A A A A A
A A A B
A B B B
A B C C
等
只要相加不得和不大于target即可进行尝试
剩下的就是保证 dfs过程不重不漏
为了避免 选择A后再选择B又回头选择A 那么ABA
和AAB就造成重复
所以每次DFS会规定选择集合的起点idx

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> v;
    int sum;
    void dfs(const vector<int>& candidates,const int target,int idx){
       if(sum > target || idx >= candidates.size())  return;
       else if(sum == target){
           ans.push_back(v);return;
       } 
        for(int i = idx; i < candidates.size();i++){
            sum += candidates[i];
            v.push_back(candidates[i]);
            dfs(candidates,target,i);
            sum -= candidates[i];
            v.pop_back();
        }

        return;
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> v;   sum = 0;  
        dfs(candidates,target,0);
        return ans;
    }
};

Leetcode 39. 组合总和 dfs

原文：https://www.cnblogs.com/itdef/p/14617064.html