class Solution {
List> result = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> combine(int n, int k) {
combineHelper(n, k, 1);
return result;
}
private void combineHelper(int n, int k, int startIndex){
//终止条件
if (path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
path.add(i);
combineHelper(n, k, i + 1);
path.removeLast();
}
}
}
【题目2】
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
class Solution {
List> result = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> combinationSum3(int k, int n) {
backTracing(k,n,0,1);
return result;
}
public void backTracing(int k,int n,int sum, int startIndex){
if(sum > n)
return;
if(path.size() == k ){
if(n == sum)
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i<= 10 - (k-path.size());i++){
sum+=i;
path.add(i);
backTracing(k,n,sum,i+1);
sum-=i;
path.removeLast();
}
}
}
【题目3】不同集合取组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
List list = new LinkedList<>();
StringBuilder temp = new StringBuilder();
public List letterCombinations(String digits) {
if(digits == null || digits.length() == 0)
return list;
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backTracing(digits,numString,0);
return list;
}
public void backTracing(String digits,String[] numString,int num){
if(num == digits.length()){
list.add(temp.toString());
return;
}
String str = numString[digits.charAt(num)-'0'];
for(int i = 0;i
【题目4】
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
我举过例子，如果是一个集合来求组合的话，就需要startIndex，
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，
注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我再讲解排列的时候就重点介绍。
class Solution {
List> result = new ArrayList<>();
LinkedList path = new LinkedList<>();
public List> combinationSum(int[] candidates, int target) {
backTracing(candidates,target,0,0);
return result;
}
public void backTracing(int[] candidates,int target,int sum,int startIndex){
if(sum > target)
return;
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex;i
//===============================剪枝优化=================
for(int i = startIndex;i target)
break;
path.add(candidates[i]);
backTracing(candidates,target,sum+candidates[i],i);
path.removeLast();
}
//但是要注意，必须排序，要不然不能全部遍历到所有组合，会直接break掉。
//但是要注意，必须排序，要不然不能全部遍历到所有组合，会直接break掉。
//但是要注意，必须排序，要不然不能全部遍历到所有组合，会直接break掉。
【题目5】 设计去重操作 遍历之前Arrays.sort(candidates);
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
去重细节
class Solution {
List> lists = new ArrayList<>();
Deque deque = new LinkedList<>();
int sum = 0;
public List> combinationSum2(int[] candidates, int target) {
//为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
//加标志数组，用来辅助判断同层节点是否已经遍历
boolean[] flag = new boolean[candidates.length];
backTracking(candidates, target, 0, flag);
return lists;
}
public void backTracking(int[] arr, int target, int index, boolean[] flag) {
if (sum == target) {
lists.add(new ArrayList(deque));
return;
}
for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
//出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {
continue;
}
flag[i] = true;
sum += arr[i];
deque.push(arr[i]);
//每个节点仅能选择一次，所以从下一位开始
backTracking(arr, target, i + 1, flag);
int temp = deque.pop();
flag[i] = false;
sum -= temp;
}
}
}
