Skip to content

Latest commit

 

History

History
57 lines (51 loc) · 3.23 KB

40. Combination Sum II.md

File metadata and controls

57 lines (51 loc) · 3.23 KB

思路

题意:从一个数组candidates(允许存在重复元素)里面选一些数字出来,使这些数字的和恰好为target,candidates里的数只能使用一次。可见这题与39. Combination Sum有两个不同点:

  1. 在挑选数字出来时,candidates里的数只能使用一次;
  2. candidates里的元素允许重复;

上面两个不同点也对应于代码中两个不同点(见下面的代码)。

思路其实和39题类似的,建议先去看看我写的39题题解
仍然是一个回溯题(类似DFS),为了避免得到重复结果,先对数组进行排序(常规操作)。
为了进行递归调用,我们定义了一个函数helper,传入的参数有

  • nums - 当前被选中的数
  • candidates - 就是题意里面的数组(从小到大排序好的)
  • start - 只能考虑数组candidates下标为start及后面的数
  • curr_target - 当前的目标(我们希望的就是nums的元素和加上curr_target就等于target)

helper函数定义如下:

  • curr_target == 0时,说明nums的元素和就等于target,nums就是一组我们要求的数,push进结果数组即可。
  • start >= candidates.size()时,说明start已经超过了candidates最大下标,返回即可;
  • candidates[start] > curr_target时,说明candidates中(当前可用的)最小的数都比curr_target大,也是直接返回。

--------------上面都和39题一样的,只是下面有两个不同点---------------

  • 前面三个条件都不满足时,假设k = candidates[start]就有两条路要走:
    1. 将k加入到nums中,令curr_target = curr_target - kstart = start+1, 进入下一层递归;
    2. 不将k加入到nums中, 由于candidates里的元素允许重复,所以candidates[start+1]也就可能等于k,所以我们应该让start移动到最后一个k所在位置,再令start + 1进入下一层递归;

C++

class Solution {
private:
    vector<vector<int>>res;
    void helper(vector<int>& nums, const vector<int>& candidates, int start, const int& curr_target){
        if(curr_target == 0){
            res.push_back(nums);
            return;
        }
        if(start >= candidates.size() || candidates[start] > curr_target) return;

        nums.push_back(candidates[start]);
        helper(nums, candidates, start + 1, curr_target - candidates[start]); // 不同点一,39传入的是start,因为39允许多次使用candidates里的数
        nums.pop_back();
        // 不同点二,因为candidates里的元素允许重复,所以要跳过这些重复元素
        while(start < candidates.size() - 1 && candidates[start] == candidates[start+1])
            start++;
        helper(nums, candidates, start + 1 , curr_target);
        return;
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if(candidates.empty()) return res;
        sort(candidates.begin(), candidates.end());
        vector<int>nums;
        helper(nums, candidates, 0, target);
        return res;
    }
};