- 组合总和
candidates 中的数字可以无限制重复被选取
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(candidates.length == 0 || candidates == null || target <= 0) return res;
// 先将数组排序避免重复搜素
Arrays.sort(candidates);
helper(candidates, target, 0, new LinkedList<Integer>(), res);
return res;
}
private void helper(int[] nums, int target, int index, List<Integer> tmp, List<List<Integer>> res) {
if (target == 0) {
res.add(new LinkedList<Integer>(tmp));
return;
} else {
// 选取之后的每个数字都是一种可能性
for (int i = index; i < nums.length; i++) {
if (target < nums[i] ){
return;
}else{//DFS
tmp.add(nums[i]);
helper(nums, target - nums[i], i, tmp, res);
tmp.remove(tmp.size() - 1);
}
}
}
}
}
- 组合总和 II
candidates 中的每个数字在每个组合中只能使用一次(递归调用时i+1)
解集不能包含重复的组合(每个递归方法内部相等的值只加入一次)
if (i > index && nums[i] == nums[i - 1]) continue;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0) {
return res;
}
Arrays.sort(candidates);
helper(candidates, 0, new ArrayList<Integer>(), target, res);
return res;
}
private void helper(int[] nums, int index, List<Integer> temp, int target,
List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<Integer>(temp));
return;
}
for (int i = index; i < nums.length; i++) {
if (i > index&& nums[i] == nums[i - 1]) {
continue;
}
if (target < nums[i]) {
return;
}
temp.add(nums[i]);
helper(nums, i + 1, temp, target - nums[i], res);
temp.remove(temp.size() - 1);
}
}
}
- 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，组合中只含有 1 - 9 的正整数
每种组合中不存在重复的数字(递归调用时i+1)
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
if( n < 1 || k < 1) return res;
helper(k, n, 1, new ArrayList<Integer>(), res);
return res;
}
private void helper(int k, int n, int index, List<Integer> tmp, List<List<Integer>> res) {
if(n == 0 && k == 0) {
res.add(new ArrayList(tmp));
return;
} else if(n < 0 || k == 0) return;//k个数相加和小于n||不到k个数和已经大于n
for(int i = index; i <= 9; i++) {
tmp.add(i);
helper(k - 1, n - i, i + 1, tmp, res);
tmp.remove(tmp.size() - 1);
}
}
}
方法二
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
if( n < 1 || k < 1) return res;
helper(k, n, 1, new ArrayList<Integer>(), res);
return res;
}
private void helper(int k, int n, int index, List<Integer> temp, List<List<Integer>> res) {
if (k < temp.size()) {//k个数相加和小于n
return;
}
if (n == 0 && temp.size() == k) {
res.add(new ArrayList<Integer>(temp));
return;
}
for (int i = index; i <= 9; i++) {
if (n < i) {
return;
}
temp.add(i);
helper(k, n - i, i + 1, temp, res);
temp.remove(temp.size() - 1);
}
}
}
