- 組合總和
candidates 中的數(shù)字可以無限制重復(fù)被選取
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;
// 先將數(shù)組排序避免重復(fù)搜素
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 {
// 選取之后的每個(gè)數(shù)字都是一種可能性
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 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次(遞歸調(diào)用時(shí)i+1)
解集不能包含重復(fù)的組合(每個(gè)遞歸方法內(nèi)部相等的值只加入一次)
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 個(gè)數(shù)的組合，組合中只含有 1 - 9 的正整數(shù)
每種組合中不存在重復(fù)的數(shù)字(遞歸調(diào)用時(shí)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個(gè)數(shù)相加和小于n||不到k個(gè)數(shù)和已經(jīng)大于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個(gè)數(shù)相加和小于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);
}
}
}
