leetcode：40. 组合总和 II

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

示例：

  1. 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  2. 输出:
  3. [
  4. [1,1,6],
  5. [1,2,5],
  6. [1,7],
  7. [2,6]
  8. ]
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

解答 & 代码

递归回溯

class Solution {
private:
    vector<vector<int>> resultList;
    vector<int> curCombine;        // 当前路径

    void backTrack(vector<int>& candidates, int start, int target)
    {
        // bad case：达到目标和，找到符合条件的组合，存入结果数组，直接返回
        if(target == 0)
        {
            resultList.push_back(curCombine);
            return;
        }
        // bad case：如果下标越界，或者剩余元素都大于 target（剪枝），则直接返回
        if(start == candidates.size() || target < candidates[start])
            return;

        // 回溯算法标准框架
        for(int i = start; i < candidates.size() && candidates[i] <= target; ++i)
        {
            // 剪枝逻辑：如果发现 nums[i] == nums[i-1]，则跳过，避免重复
            if(i == start || candidates[i] != candidates[i - 1])
            {
                // 做选择
                curCombine.push_back(candidates[i]);
                // 递归遍历下一层回溯树
                backTrack(candidates, i + 1, target - candidates[i]);
                // 撤销选择
                curCombine.pop_back();
            }
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 先排序，让相同的元素靠在一起
        sort(candidates.begin(), candidates.end());
        backTrack(candidates, 0, target);
        return resultList;
    }
};

复杂度分析：

  • 时间复杂度 O()：
  • 空间复杂度 O(N)：

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 42.60% 的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了 25.09% 的用户