题目描述
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
样例
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
算法1
(DFS +回溯) $O(n * 2^n)$
这题是基于LeetCode 39 来做的。
思想:1.终止条件:题目说当组合中的总和 == target 时,这个组合就是答案,所以当target == 0 时,退出递归。在递归过程中有可能target < 0,所以终止条件是: target <= 0
2.因为要找出nums 数组中所有可能使数字和 == target 的组合,所以要遍历整个数组,利用for循环遍历数组。
3.从LeetCode 39 中得到思想:不能够使用之前的数再次重组成答案,所以要用一个变量来规定好遍历数组时的起始位置:index。
4.题目说所有数只能被使用一次,也就是说nums 数组中可能会出现同一个数出现多次的情况,那么造成的结果就是:当nums 数组有序的情况下,前一个数的组合答案中已经包括了当前数的组合答案了,所以当遇到这种情况时,就要选择跳过当前值,不用给当前值进行组合。
时间复杂度
每个数都有两种状态,即2^n,且有n 个数,那么整体时间复杂度:O(n * 2^n)
参考文献
Java 代码
public class 组合总和II {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path;
public List<List<Integer>> combinationSum2(int[] nums, int target) {
if(nums.length == 0) return res;
path = new ArrayList<>();
Arrays.sort(nums);
dfs(nums,0,target);
return res;
}
void dfs(int[] nums,int index,int target){
if(target <= 0){
if(target == 0){
res.add(new ArrayList<>(path));
}
return;
}
for(int i = index; i < nums.length; i++){
if(i > index && nums[i] == nums[i - 1]){
continue;
}
path.add(nums[i]);
//因为每次组合不能出现重复的数组,所以每一次递归的遍历数组
//都是基于上一次递归中遍历的最终位置的后一位来开始遍历
dfs(nums,i + 1,target - nums[i]);
path.remove(path.size() - 1);
}
}
}