组合总和

题目

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

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

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

思路

1. 对candidates进行从小到大的排序，然后去除其中大于taeget的元素，其余的为我们的候选元素
2. 在第一个循环中，遍历候选元素的每个值，然后递归，再次从候选元素的第一个值开始选择，若小于target，就接着递归，而不是继续在本次递归中继续循环。若大于则直接跳出，若等于则加入res，跳出。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> elem;
    vector<int> ProcessCandidates(vector<int> candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        for(auto iter = candidates.begin(); iter < candidates.end(); ++iter)
        {
            if(*iter > target) 
            {
                candidates.erase(iter, candidates.end());
                return candidates;
            }
        }
        return candidates;
    }
    bool IsINRes(vector<int> elem2)
    {
        for(int i = 0; i < res.size(); ++i)
        {
            if(res[i].size() == elem2.size())
            {
                sort(elem2.begin(), elem2.end());
                sort(res[i].begin(), res[i].end());
                int j;
                for(j = 0; j < elem.size(); ++j)
                {
                    if(elem2[j] != res[i][j]) break;
                }
                if(j == elem2.size()) return true;
            }
        }
        return false;
    }
    void combinationSumAux(vector<int>& candidates, int target)
    {
        for(int i=0; i<candidates.size(); ++i)
        {
            if(target - candidates[i] < 0)
            {
                return;
            }
            else if(target - candidates[i] == 0)
            {
                elem.emplace_back(candidates[i]);
                if(!IsINRes(elem))  res.emplace_back(elem);
                elem.pop_back();
                return;
            }
            else
            {
                elem.emplace_back(candidates[i]);
                combinationSumAux(candidates, target - candidates[i]);
                elem.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> filter_candidates = ProcessCandidates(candidates, target);
        combinationSumAux(filter_candidates, target);
        return res;
    }
};

将近一个小时写出来的，哈哈哈，不过效率太低了，在重复问题上花费了太多资源

看完代码随想录，在重复上忽略了很重要的一点，其实在选取时，可以采取一些策略，使每种组合不会发生重复。其实和普通的组合没有太大差别，可以找例子先手动模拟一下

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

剪枝操作

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0, 0);
        return result;
    }
};