40. 组合总和II
回溯
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class Solution {
List> list = new LinkedList<>();
LinkedList li = new LinkedList<>();
public List> combinationSum2(int[] candidates, int target) {
/**
* 比较相邻的数字是否相等可以判断数字是否重复,因此数组要先排序
*/
Arrays.sort(candidates);
backtracking(candidates, target, 0);
return list;
}
public void backtracking(int[] candidates, int target, int startIndex){
if (target == 0){
list.add(new LinkedList<>(li));
return;
}
if (target < 0) {
return;
}
/**
* 在同一层for循环中,如果i > startIndex时相邻的数字相等,说明发生了重复,因此不能取这个数字
*/
for (int i = startIndex; i < candidates.length; i++) {
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
li.add(candidates[i]);
backtracking(candidates, target - candidates[i], i + 1);
li.removeLast();
}
}
}
/**
* 时间复杂度 O(n×2^n)
* 空间复杂度 O(n)
*/
https://leetcode-cn.com/problems/combination-sum-ii/