leetcode39(组合总数)

leetcode39-组合总数，经典的回溯算法应用。

leetcode-39 组合总数（9/9）

给定一个无重复元素的数组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]
]

solution：

经典的回溯法的应用，注意题目中求解的是组合。

回溯模板:

backtracking() {
    if (终止条件) {
        存放结果;
    }

    for (选择：选择列表（可以想成树中节点孩子的数量）) {
        递归，处理节点;
        backtracking();
        回溯，删除节点；
    }
};

C++代码：

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> path;
    void BackTracking(vector<int>& candidates,int target,int sum,int index){
        if(sum>target) return;
        if(sum==target){
            ans.push_back(path);
            return;
        }
        for(int i=index;i<candidates.size();i++){//组合从index开始，排列从0开始
            sum+=candidates[i];
            path.push_back(candidates[i]);
            BackTracking(candidates,target,sum,i);//i表示允许重复使用元素，不允许则是i+1
            sum-=candidates[i];
            path.pop_back();
        }

    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        BackTracking(candidates,target,0,0);
        return ans;
    }
};

end!

赏

谢谢大家的打赏！

支付宝