LeetCode回溯&递归

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

String[] letter={" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

private List<String> res=new LinkedList<>();

public List<String> letterCombinations(String digits) {
    //空字符串要注意
    if ("".equals(digits)) return res;
    letterCombinations(digits,0,"");
    return res;
}

public void letterCombinations(String digits,int index,String str) {
    //递归出口，当 index==digits 的长度的时候就说明走到尽头了
    //需要回头尝试其他的情况
    if (index==digits.length()) {
        res.add(str);
        return;
    }
    //当前字符对应的字母组合
    char[] ls=letter[digits.charAt(index)-48].toCharArray();
    //遍历每种可能，其实就是 DFS
    for (int i=0;i<ls.length;i++) {
        letterCombinations(digits,index+1,str+ls[i]);
    }
    return;
}

输入："25525511135"
输出：["255.255.11.135", "255.255.111.35"]

public List<String> restoreIpAddresses(String s) {
    restoreIpAddresses(s,0,"",0);
    return res;
}

LinkedList<String> res=new LinkedList<>();

public void restoreIpAddresses(String s,int index,String des,int count) {
    if (count>4) {
        return;
    }
    //到字符串末尾了
    if (index==s.length()) {
        if (count==4) {
            res.add(des.substring(0,des.length()-1));    
        }
        return;
    }
    //如果为 0 就不用切分了，这里就相当于直接跳过
    if (s.charAt(index)=='0') {
        restoreIpAddresses(s,index+1,des+"0.",count+1);
    }else{
        //不为 0 就需要继续切分为 1，2，3
        //切分过程中需要注意要小于 255, 同时需要一个计数器来判度是否终止
        for (int i=1;i<4;i++) {
            if (index+i<=s.length()) {
                String temp=s.substring(index,index+i);
                if (Integer.valueOf(temp)<=255){
                    restoreIpAddresses(s,index+i,des+temp+".",count+1);    
                }
            }
        }
    }
}

func restoreIpAddresses(s string) []string {
    var res []string
    if len(s) < 4 || len(s) > 12 {
        return res
    }
    var dfs func(s string, lis []string)
    dfs = func(s string, lis []string) {
        if s == "" {
            if len(lis) == 4 {
                res = append(res, strings.Join(lis, "."))
            }
            return
        }
        //s 未遍历完就集齐了 4 块
        if len(lis) >= 4 {
            return
        }
        for i := 1; i <= 3; i++ {
            if i <= len(s) && check(s[:i]) {
                lis = append(lis, s[:i])
                dfs(s[i:], lis)
                lis = lis[:len(lis)-1]
                //前导 0 的处理，读取 0 之后就不再向后扩展
                if s[:i] == "0" {
                    return
                }
            }
        }
    }
    dfs(s, []string{})
    return res
}

func check(s string) bool {
    if ns, _ := strconv.Atoi(s); ns <= 255 {
        return true
    }
    return false
}

输入："aab"
输出：
[
  ["aa","b"],
  ["a","a","b"]
]

public List<List<String>> partition(String s) {
    partition(s,0,new ArrayList());
    return res;
}   

List<List<String>> res=new ArrayList<>();

public void partition(String s,int index,List<String> lis) {
    if (index==s.length()) {
        //注意这里要 copy 一个 list 不能直接添加 lis
        //lis 引用的对象后面还会继续变化，最后会变为 null
        res.add(new ArrayList(lis));
        return;
    }
    for (int i=index+1;i<=s.length();i++) {
        String temp=s.substring(index,i);
        //System.out.println(index+"="+i+"="+temp);
        if (isPalind(temp)) {
            lis.add(temp);
            partition(s,i,lis);
            //不能直接 remove(temp), 主要是会有重复的字符，所以会导致最后的顺序不一致，而且效率也很低
            //lis.remove(temp);
            lis.remove(lis.size()-1);
        }
    }
}

public boolean isPalind(String s){
    for (int i=0,j=s.length()-1;i<=j;i++,j--) {
        if (s.charAt(i)!=s.charAt(j)) {
            return false;
        }
    }
    return true;
}

输入：[1,2,3]
输出：
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

public List<List<Integer>> permute(int[] nums) {
    if (nums==null || nums.length<=0) {
        return res;
    }
    boolean[] visit=new boolean[nums.length];
    permute(nums,new ArrayList(),visit);
    return res;
}

private List<List<Integer>> res=new ArrayList<>();

public void permute(int[] nums,List<Integer> lis,boolean[] visit) {
    if (lis.size()==nums.length) {
        res.add(new ArrayList(lis));
        return;
    }
    for (int i=0;i<nums.length;i++) {
        if (visit[i]) continue;
        lis.add(nums[i]);
        visit[i]=true;
        permute(nums,lis,visit);
        //回溯
        visit[i]=false;
        lis.remove(lis.size()-1);
    }
}

输入：n = 3, k = 3
输出："213"

输入：n = 4, k = 9
输出："2314"

public String getPermutation(int n, int k) {
    boolean[] visit=new boolean[n+1];
    getPermutation(n,k,0,visit,new StringBuilder(""));
    return res.get(k-1).toString();
}

private List<StringBuilder> res=new LinkedList<>();

public void getPermutation(int n, int k,int count,boolean[] visit,StringBuilder str) {
    if (count == n) {
        res.add(new StringBuilder(str));
        return;
    }
    if (res.size()==k) {
        return;
    }
    for (int i=1;i<=n;i++) {
        if (!visit[i]) {
            str.append(i);
            visit[i]=true;
            getPermutation(n,k,count+1,visit,str);
            visit[i]=false;
            str.delete(str.length()-1,str.length());
        }
    }
}

输入：n = 1, k = 3
输出："c"
解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。

输入：n = 1, k = 4
输出：""
解释：长度为 1 的开心字符串只有 3 个。

输入：n = 3, k = 9
输出："cab"
解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"

输入：n = 2, k = 7
输出：""

输入：n = 10, k = 100
输出："abacbabacb"

public String getHappyString(int n, int k) {
    dfs("a",n,k);
    dfs("b",n,k);
    dfs("c",n,k);
    return res;
}

private int count=0;

private String res="";

public void dfs(String cur,int n,int k){
    if(!"".equals(res)) return;
    if(cur.length()==n){
        count++;
        if(count==k){
            res=cur;
        }
        return;
    }
    char last=cur.charAt(cur.length()-1);
    if(last=='a'){
        dfs(cur+'b',n,k);
        dfs(cur+'c',n,k);
    }
    if(last=='b'){
        dfs(cur+'a',n,k);
        dfs(cur+'c',n,k);
    }
    if(last=='c'){
        dfs(cur+'a',n,k);
        dfs(cur+'b',n,k);
    }
}

输入：[1,1,2]
输出：
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

public List<List<Integer>> permuteUnique(int[] nums) {
    if (nums==null || nums.length<=0) {
        return res;
    }
    //Arrays.sort(nums); 解法二需要先排序
    boolean[] visit=new boolean[nums.length];
    permuteUnique(nums,new ArrayList(),visit);
    return res;
}

private List<List<Integer>> res=new ArrayList<>();

public void permuteUnique(int[] nums,List<Integer> lis,boolean[] visit){
    HashSet<Integer> set=new HashSet<>();
    if (lis.size()==nums.length) {
        res.add(new ArrayList(lis));
        return;
    }
    for (int i=0;i<nums.length;i++) {
        if (!visit[i] && !set.contains(nums[i])) {
            lis.add(nums[i]);
            visit[i]=true;
            set.add(nums[i]);
            permuteUnique(nums,lis,visit);
            visit[i]=false;
            lis.remove(lis.size()-1);
        }
    }
}

//需要排序
public void permuteUnique2(int[] nums,List<Integer> lis,boolean[] visit){
    if (lis.size()==nums.length) {
        res.add(new ArrayList(lis));
        return;
    }
    for (int i=0;i<nums.length;i++) {
        //剪枝去重，和前一个元素比较
        //Bug 警告，应该写！visit[i-1]
        if (i>0&&nums[i]==nums[i-1] && !visit[i-1]) 
            continue;
        if (!visit[i]) {
            lis.add(nums[i]);
            visit[i]=true;
            permuteUnique2(nums,lis,visit);
            visit[i]=false;
            lis.remove(lis.size()-1);
        }
    }
}

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

private LinkedList<String> res=new LinkedList<>();

//abc
public CombinationIterator(String characters, int combinationLength) {
    dfs("",combinationLength,0,0,characters);
}

public String next() {
    return res.pollFirst();
}

public void dfs(String cur,int len,int index,int count,String source) {
    if (count == len) {
        res.add(cur); //直接根据 cur 得长度判断就 ok 了
        return;
    }
    for (int i=index;i<source.length();i++) {
        dfs(cur+source.charAt(i),len,i+1,count+1,source);
    }
}

public boolean hasNext() {
    return !res.isEmpty();
}

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

public List<List<Integer>> combine(int n, int k) {
    if (k>n || n<=0 ||k<=0) {
        return res;
    }
    //boolean[] visit=new boolean[n+1];
    combine(n,k,1,new ArrayList(),0);
    return res;
}   

private List<List<Integer>> res=new ArrayList<>();

//剪枝优化 1
public void combine(int n, int k,int index,List<Integer> lis,int count) {
    if (count==k) {
        res.add(new ArrayList(lis));
        return;
    }
    //1 2 3 4 | 3
    //index = 3 k=3  n=4 count=0 (3 为头，显然是不行的，肯定会和前面重复） --> 3<=3
    //index = 3 k=3  n=4 count=1 (3 为第二个，是可行的） --> 3 <= 2
    if (n-index+2<=k-count) {
        return;
    }
    for (int i=index;i<=n;i++) {
        lis.add(i);
        combine(n,k,i+1,lis,count+1);
        //回溯的关键
        lis.remove(lis.size()-1);
    }
}

//剪枝优化 2
public void combine4(int n, int k,int index,List<Integer> lis,int count) {
    if (count==k) {
        res.add(new ArrayList(lis));
        return;
    }
    //循环的区间至少要有 k-count 个元素 也就是 [i,N] 之间至少要有 k-count 个元素
    //N-i+1>=k-count --> i<=n-(k-count)+1
    for (int i=index;i<=n-(k-count)+1;i++) {
        lis.add(i);
        combine4(n,k,i+1,lis,count+1);
        //回溯的关键
        lis.remove(lis.size()-1);
    }
}

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates==null || candidates.length<=0) {
        return res;
    }
    combinationSum(candidates,target,0,0,new ArrayList());
    return res;
}

private List<List<Integer>> res=new ArrayList<>();

public void combinationSum(int[] candidates, int target,int index,int sum,List<Integer> lis) {
    if (sum>target) {
        return;
    }
    if (target==sum) {
        res.add(new ArrayList(lis));
        return;
    }
    //这里一次循环其实就确定了包含 i 的所有可能解，所以起点是 index 不是 0
    for (int i=index;i<candidates.length;i++) {
        //跳过比 target 大的
        if (candidates[i]>target) continue;
        sum+=candidates[i];
        lis.add(candidates[i]);
		//其实主要就是搞清楚每次从哪里开始，以及每次循环的作用
        //可以重复选取自己，所以子递归也从 i 开始而不是 i+1
        combinationSum(candidates,target,i,sum,lis);
        sum-=candidates[i];
        lis.remove(lis.size()-1);
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates==null || candidates.length<=0) {
        return res;
    }
    //排序，方便剪枝
    Arrays.sort(candidates);
    combinationSum(candidates,target,0,0,new ArrayList());
    return res;
}

private List<List<Integer>> res=new ArrayList<>();

//剪枝优化 2
public void combinationSum(int[] candidates, int target,int index,int sum,List<Integer> lis) {
    if (sum>target) {
        return;
    }
    if (target==sum) {
        res.add(new ArrayList(lis));
        return;
    }
    for (int i=index;i<candidates.length;i++) {
        if (sum+candidates[i]>target) return;
        sum+=candidates[i];
        lis.add(candidates[i]);
        //注意这里传递进去的 index 是 i
        combinationSum(candidates,target,i,sum,lis);
        sum-=candidates[i];
        lis.remove(lis.size()-1);
    }
}

输入：candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为：
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

输入：candidates = [2,5,2,1,2], target = 5,
所求解集为：
[
  [1,2,2],
  [5]
]

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if (candidates ==null || candidates.length<=0) {
        return res;
    }
    Arrays.sort(candidates);
    combinationSum2(candidates,target,0,new ArrayList());
    return res;
}

public void combinationSum2(int[] candidates, int target,int index,List<Integer> lis) {
    /*if (target<0) {
            return;
        }*/
    if (target==0) {
        res.add(new ArrayList(lis));
        return;
    }

    for (int i=index;i<candidates.length;i++) {
        //注意这里 i>index
        if (i>index && candidates[i]==candidates[i-1]  ) continue;
        //排过序的，可以直接 return
        if (target-candidates[i]<0) return;
        lis.add(candidates[i]);
        combinationSum2(candidates,target-candidates[i],i+1,lis);
        lis.remove(lis.size()-1);
    }
}

输入：k = 3, n = 7
输出：[[1,2,4]]

输入：k = 3, n = 9
输出：[[1,2,6], [1,3,5], [2,3,4]]

//UPDATE: 2020.9.11
func combinationSum3(k int, n int) [][]int {
    var res [][]int
    var dfs func(idx int, sum int, lis []int)
    dfs = func(idx int, sum int, lis []int) {
        if len(lis) > k {
            return
        }
        if sum == n && len(lis) == k {
            dest := make([]int, len(lis))
            copy(dest, lis)
            res = append(res, dest)
            return
        }
        for i := idx; i <= 9; i++ {
            if sum + i > n {
                return
            }
            dfs(i+1, sum+i, append(lis, i))
        }
    }
    dfs(1, 0, []int{})
    return res
}

func combinationSum3(k int, n int) [][]int {
    var res [][]int
    for i := 0; i < (1<<9); i++ {
        var sum, cnt = 0, 0
        var lis []int
        for j := 0; j < 9; j++ {
            if i & (1<<j) != 0 {
                sum += j+1
                cnt++
                lis = append(lis, j+1)
            }
        }
        if sum == n && cnt == k {
            res = append(res, lis)   
        }
    }
    return res
}

输入：nums = [1,2,3]
输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

private List<List<Integer>> res=new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
    if (nums==null || nums.length<=0) {
        return res;
    }
    subsets(nums,0,new ArrayList());
    return res;
}

public void subsets(int[] nums,int index,List<Integer> lis) {
    //if (index<=nums.length) {
        res.add(new ArrayList(lis));
    //}
    for (int i=index; i<nums.length;i++) {
        lis.add(nums[i]);
        subsets(nums,i+1,lis);
        lis.remove(lis.size()-1);
    }
}

func subsets(nums []int) [][]int {
    var res [][]int
    var lis []int
    var dfs func(index int)
    dfs = func(index int){
        dest:=make([]int,len(lis))
        copy(dest,lis)
        res=append(res,dest)
        for i:=index;i<len(nums);i++{
            lis=append(lis,nums[i])
            dfs(i+1)
            lis=lis[:len(lis)-1]
        }
    }
    dfs(0)
    return res
}

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> queue=new ArrayList<>();
    if (nums==null || nums.length<=0) {
        return queue;
    }
    queue.add(new ArrayList());
    for (int i=0;i<nums.length;i++) {
        int next=queue.size();
        for (int j=0;j<next;j++) {
            List<Integer> temp=new ArrayList(queue.get(j));
            temp.add(nums[i]);
            queue.add(temp);
        }
    }
    return queue;
}

func subsets(nums []int) [][]int {
    var n = len(nums)
    var res [][]int
    for i := 0; i < (1<<n); i++ {
        var lis []int
        for j := 0; j < n; j++ {
            if i & (1<<j) != 0 {
                lis = append(lis, nums[j])
            }
        }
        res = append(res, lis)
    }
    return res
}

输入：[1,2,2]
输出：
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public List<List<Integer>> subsetsWithDup(int[] nums) {
    if (nums==null || nums.length<=0) {
        return res;
    }
    //需要先排序，便于跳过相同的元素
    Arrays.sort(nums);
    subsets(nums,0,new ArrayList());
    return res;
}

private  List<List<Integer>> res=new ArrayList<>();

public void subsets(int[] nums,int index,List<Integer> lis) {
    res.add(new ArrayList(lis));
    for (int i=index;i<nums.length;i++) {
        if (i>index && nums[i] == nums[i-1]) {
            continue;
        }
        lis.add(nums[i]);
        subsets(nums,i+1,lis);
        lis.remove(lis.size()-1);
    }
}

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    var lis []int
    var dfs func(index int)
    dfs = func(index int){
        dest:=make([]int,len(lis))
        copy(dest,lis)
        res=append(res,dest)
        for i:=index;i<len(nums);i++{
            if i>index && nums[i]==nums[i-1]{
                continue
            }
            lis=append(lis,nums[i])
            dfs(i+1)
            lis=lis[:len(lis)-1]
        }
    }
    dfs(0)
    return res
}

输入：2
输出：91 
解释：答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

//这种可以做记忆化，0ms
Integer[] cache=null;

public int countNumbersWithUniqueDigits2(int n) {
    boolean[] visit=new boolean[10];
    cache=new Integer[n+1];
    int res=0;
    if (n==0) return 1;
    for (int i=1;i<=9;i++) { //不考虑 0 开头的
        visit[i]=true;
        res+=countNumbersWithUniqueDigits2(n,visit,1);
        visit[i]=false;
    }
    return res+1; //加的是 0 这种情况
}

//[index,n](位数)区间内，能构成最多的不重复数字
public int countNumbersWithUniqueDigits2(int n,boolean[] visit,int index){
    if (index==n) { //没得选，只有一种
        return 1;
    }
    if (cache[index]!=null) {
        return cache[index];
    }
    int count=1;
    for (int i=0;i<=9;i++) {
        if (!visit[i]) {
            visit[i]=true;
            count+=countNumbersWithUniqueDigits2(n,visit,index+1);
            visit[i]=false;
        }
    }
    return cache[index]=count;
}