解法一:回溯

思路步骤:

涉及到搜索所有可能的组合类型时,一般情况下都会想到用回溯法。题目中结果集不能重复,这是一个应该注意的点。

  • 开两个数组rseultpath存储结果与可能的路径集。

  • 处理递归终止情况:sum+=num[i]>target时,终止循环(sum为组合数和)

  • 利用一个num.size()大小的数组used进行去重。

  • 参考图解:
    图片说明

C++参考代码:

class Solution {
private:
        //回溯函数
    vector<vector<int>> result;//原来存储最终结果的数组
    vector<int> path;//存储符合条件的路径集
    void backtracking(vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){
        if(sum==target){
            result.push_back(path);
            return;
        }
       //循环+剪枝   :去重的具体代码:used[i-1]==false
        //剪枝的具体代码:sum+candidates[i]<=target;
       for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;i++){
           if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false){
               continue;
           }
           //累加求和
           sum+=candidates[i];
           path.push_back(candidates[i]);
            //更新used数组状态
           used[i]=true;
            //回溯(递归)函数调用
           backtracking(candidates, target,sum,i+1,used);
           used[i]  =false;
           sum-=candidates[i];//回溯
           path.pop_back();//回溯
       }
    }
public:
    vector<vector<int>> combinationSum2(vector<int> &num, int target) {
        vector<bool> used(num.size(), false);
        //STL中vector的排序函数