组合问题

力扣77组合(剪枝优化)，216组合总和，17电话号码的组合，39组合总和1(可使用重复元素，但数组中不包含相同元素)，40组合总和2(不可重复使用相同元素，但数组中含有相同的元素就可以使用)，113分割回文串
1. 77组合

private List<List<Integer>>res=new ArrayList<>();
private List<Integer>singleRes=new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
  backTrack(n,k,1);
  return res;
}
private void backTrack(int n,int k,int index){
  if(singleRes.size()==k){
    res.add(new ArrayList<>(singleRes));
    return;
  }
  for(int i=index;i<=n;i++){
    singleRes.add(i);
    backTrack(n,k,i+1);
    singleRes.remove(singleRes.size()-1);
  }
}
}
如果剪枝的话就是
for(int i=index;i<=n-(k-singleRes.size())+1;i++){
自己用n=4,k=4来试试效果。

    216组合总和

private void backTrack(int k,int n,int index){
  if(singleRes.size()==k){
    if(sum==n){
      res.add(new ArrayList<>(singleRes));
      return;
    }else{
      return;
    }
  }
  for(int i=index;i<=9;i++){
    singleRes.add(i);
    sum+=i;
    backTrack(k,n,i+1);
    singleRes.remove(singleRes.size()-1);
    sum-=i;
  }
}

14电话号码的字母组合

private List<String>res=new ArrayList<>();
private StringBuilder sb=new StringBuilder();
private String[] reflection=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
  if(digits.equals("")||digits.length()==0){
    return res;
  }
  backTrack(0,digits.length(),digits);
  return res;
}
private void backTrack(int index,int length,String digits){
  if(sb.length()==length){
    res.add(sb.toString());
    return;
  }
  for(int i=index;i<digits.length();i++){
    int location = digits.charAt(i) - '0';
    String str=reflection[location];
    for(int j=0;j<str.length();j++){
      sb.append(str.charAt(j));
      backTrack(i+1,length,digits);
      sb.deleteCharAt(sb.length()-1);
    }
  }
}

39 组合总和1（可以使用相同的数组元素）

private List<List<Integer>>res=new ArrayList<>();
private List<Integer>singleRes=new LinkedList<>();
private int sum=0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
  Arrays.sort(candidates);
  backTrack(0,candidates,target);
  return res;
}
private void backTrack(int index,int[] candidates,int target){
  if(sum==target){
    res.add(new ArrayList<>(singleRes));
    return;
  }else if(sum>target){
    return;
  }
  for(int i=index;i<candidates.length;i++){
    singleRes.add(candidates[i]);
    sum+=candidates[i];
    backTrack(i,candidates,target);
    singleRes.remove(singleRes.size()-1);
    sum-=candidates[i];
  }
}

40. 组合总和2

private List<List<Integer>>res=new ArrayList<>();
private List<Integer>singleRes=new LinkedList<>();
private int sum=0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  Arrays.sort(candidates);
  backTrack(0,candidates,target);
  return res;
}
private void backTrack(int index,int[]candidates,int target){
  if(sum==target){
    res.add(new ArrayList<>(singleRes));
    return;
  }else if(sum>target){
    return;
  }
  for(int i=index;i<candidates.length;i++){
    if(i>index&&candidates[i]==candidates[i-1]){
      continue;
    }
    singleRes.add(candidates[i]);
    sum+=candidates[i];
    backTrack(i+1,candidates,target);
    singleRes.remove(singleRes.size()-1);
    sum-=candidates[i];
  }
}

131 分割回文串

private List<List<String>>res=new ArrayList<>();
private List<String>singleRes=new LinkedList<>();
public List<List<String>> partition(String s) {
  backTrack(0,s);
  return res;
}
private void backTrack(int index,String s){
  if(index>=s.length()){
    res.add(new ArrayList<>(singleRes));
    return;
  }
  for(int i=index;i<s.length();i++){
    if(check(s,index,i)) {
      singleRes.add(s.substring(index,i+1));
      backTrack(i+1,s);
      singleRes.remove(singleRes.size()-1);
    }
  }
}
private boolean check(String s,int start,int end){
  for(int i=start,j=end;i<end;i++,j--){
    if(s.charAt(i)!=s.charAt(j)){
      return false;
    }
  }
  return true;
}