【算法与数据结构】40、LeetCode组合总和 II

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：【算法与数据结构】39、LeetCode组合总和的基础之上，这道题变成了candidates中有重复元素，而且每个元素只能使用一次。如果直接使用39题的代码会出现重复的组合，需要去重，但这样一来leetcode可能运行超时。因此我们需要再找组合的时候就进行去重的操作。引入一个used布尔数组，标记candidates中的元素是否使用过。在这之前首先需要对candidates数组进行排序。

  例如， target=7, candidates = [1 1 2 4 5 7], 第一种情况：candidates[0] +candidates[2] + candidates[3] = candidates[1] +candidates[2] + candidates[3]= 1 + 2 + 4, 因此出现重复的组合。第二种情况：candidates[0] +candidates[1] + candidates[4]= 1 + 1 + 5是无重复的组合。因此用used标记使用过的数，当candidates[i] == candidates[i - 1]时，出现重复元素。进行第i次循环时，第一种情况used[i-1]=false就是出现重复组合, 在第i-1次循环时已经考虑过了，直接continue。第二种情况就是重复数字都利用到了used[i-1]=true，这种需要考虑。
  程序如下：

class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(const vector<int>& candidates, const int target, int sum, int startIndex, vector<bool>& used) {if (sum > target) return;    // 剪枝if (sum == target) {result.push_back(path);return;}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];used[i] = true;path.push_back(candidates[i]);  // 处理节点backtracking(candidates, target, sum, i+1, used);  // 递归used[i] = false;sum -= candidates[i];path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

复杂度分析：

• 时间复杂度： $O(n\ast 2^n)$。
• 空间复杂度：$O(n)$。

三、完整代码

# include <iostream>
# include <vector>
# include <string>
# include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(const vector<int>& candidates, const int target, int sum, int startIndex, vector<bool>& used) {if (sum > target) return;    // 剪枝if (sum == target) {result.push_back(path);return;}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];used[i] = true;path.push_back(candidates[i]);  // 处理节点backtracking(candidates, target, sum, i+1, used);  // 递归used[i] = false;sum -= candidates[i];path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool>used(candidates.size(), 0);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};int main() {vector<int> candidates = { 10,1,2,7,6,1,5 };int target = 8;Solution s1;vector<vector<int>> result = s1.combinationSum2(candidates, target);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}

end