[Leetcode]40. Combination Sum II(C++)

题目描述

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

Each number in candidates may only be used once in the combination.

例子

例子 1

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

例子 2

Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]

例子 3

Input: Output: Explanation:

Follow Up

Note

The solution set must not contain duplicate combinations.

Constraints

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

解题思路

这道题在 39. Combination Sum 的基础上增加了两个条件：

每个数字只能选一次
返回的组合中不能包含的重复的子集：
- 例如，输入是 [2,2,2]，要求目标是 4 的话，结果中只能出现一次 [2,2]

因此我们需要上一道题的代码基础上进行一定修改：

DFS 内部循环递归调用时，传入的索引改成 i + 1，避免同一位置多次使用
对输入数组进行排序，在循环时如果前一位数字和当前数字一致时，跳过当前数字（因为这种情况已经考虑过了）

代码如下：

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<int> candidate;
        std::vector<std::vector<int>> result;
        std::sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target, candidate, result);
        return result;
    }
    
private:
    void dfs(const std::vector<int>& candidates, int idx, int res, std::vector<int>& candidate, std::vector<std::vector<int>>& result) {
        if (res == 0) {
            result.push_back(candidate);
        } else if (res < 0) {
            return;
        }

        for (int i = idx; i < candidates.size(); ++i) {
            if (i != idx && candidates[i] == candidates[i - 1]) continue;
            candidate.push_back(candidates[i]);
            dfs(candidates, i + 1, res - candidates[i], candidate, result);
            candidate.pop_back();
        }
    }
};

时间复杂度: O(n!)
空间复杂度: O(Cnk)

GitHub 代码同步地址： 40.CombinationSumIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions