题目描述
Given an array of distinct integers
candidates
and a target integertarget
, return a list of all unique combinations ofcandidates
where the chosen numbers sum totarget
. 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
,避免同一位置多次使用 - 对输入数组进行排序,在循环时如果前一位数字和当前数字一致时,跳过当前数字(因为这种情况已经考虑过了)
代码如下:
1 |
|
- 时间复杂度: O(n!)
- 空间复杂度: O(Cnk)
GitHub 代码同步地址: 40.CombinationSumIi.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions