leetcode 链接：40. 组合总和 II

题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

解答 & 代码

递归回溯

  1. class Solution {
  2. private:
  3.     // 递归回溯得到所有不重复的组合，存在 resultList 中
  4.     void findCombinations(vector<int> candidates, int target, int left, vector<int>& result, vector<vector<int>>& resultList)
  5.     {
  6.         // 从左边界开始遍历数组中的元素
  7.         for(int i = left; i < candidates.size() && candidates[i] <= target; ++i)
  8.         {
  9.             // 去重：如果当前元素不是左边界并且和前一个元素相同，则跳过
  10.             while(i != left && i < candidates.size() && candidates[i] == candidates[i - 1])
  11.                 ++i;
  12.             // 如果当前下标越界或者当前元素值大于 target，直接返回（已排序，后面元素只会更大，因此可剪枝）
  13.             if(i >= candidates.size() || candidates[i] > target)
  14.                 return;
  16.             result.push_back(candidates[i]);    // 选取当前元素
  18.             // 如果当前元素就等于 target，将当前的组合存入 resultList
  19.             if(candidates[i] == target)
  20.                 resultList.push_back(result);
  21.             else    // 递归寻找组合的下一个元素
  22.                 findCombinations(candidates, target - candidates[i], i + 1, result, resultList);
  24.             result.pop_back();                    // 回溯
  25.         }
  26.     }
  27. public:
  28.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  29.         sort(candidates.begin(), candidates.end()); // 升序排序（为了去重）
  30.         vector<int> result;
  31.         vector<vector<int>> resultList;
  32.         findCombinations(candidates, target, 0, result, resultList);
  33.         return resultList;
  34.     }
  35. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：12.7 MB, 在所有 C++ 提交中击败了 16.31% 的用户