总结下recursion入门的几个题

carybabywin

总结一些recursion的练习题， 跟dfs和backtracking相关的，有一些固定写法，其中也有一些区别， 例如大家比较restore ip address 和palindrome partitioning 这两个题就可以看出来，一个是不断添加同一个pattern的结果到result里， 一个是把一个pattern拆分给几个部分分别insert。感觉backtracking主要是这两大块。

01-knapsack  

                              

Maze(dfs):

Visited[][], otherwise stackoverflow

Optimize: 1. Visited【i】[j] = true  => maze【i】[j] = X(wall)

2. use dx[], dy[]

3. move condition check into for loop

Find maze path:

To return path,need backtracking.  New String, string 在java中是不可变object。

Knapsack: withduplicate number, can choose duplicate or not.

Combinationsum(leetcode 39);  i or i+1 depends onallow same number to be selected more than once.

Combination sumII(leetcode 40)

Combination sum IVP problem

Generate parentheses:Catalan number

Letter combinationof a phone number

public class Solution {

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

    public List<String> letterCombinations(String digits) {

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

        if(digits ==null||digits.length()==0){

            return res;

        }      

        helper(digits, res, "",0);

        return res;

    }

    private void helper(String digits, List<String> res, String cur, int index){

        if(cur.length() == digits.length()){

            res.add(cur);

            return;

        }

        String letters = key[digits.charAt(index)-'0'];

        for(int i=0; i<letters.length(); i++){

            cur = cur+letters.charAt(i);

            helper(digits, res, cur, index+1);

            cur = cur.substring(0,cur.length()-1);

        }

    }

}

Subset

public class Solution {

    public List<List<Integer>> subsets(int[] nums) {

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

        helper(nums, res, 0, new ArrayList<Integer>());

        return res;

    }

    private void helper(int[] nums, List<List<Integer>> res, int index, List<Integer> cur){

        res.add(new ArrayList<Integer>(cur));

        for(int i =index; i<nums.length; i++){

            cur.add(nums【i】);

            helper(nums, res, i+1, cur);

            cur.remove(cur.size()-1);

        }

    }

}

N-Queens

public class Solution {

    public List<List<String>> solveNQueens(int n) {

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

        int[] queens = new int[n];

        helper(res, n, 0, queens);

        return res;

    }

    private void helper(List<List<String>> res, int n, int index, int[] queens){

        if(index == n){

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

            for(int num:queens){

                StringBuilder sb = new StringBuilder();

                for(int j=0; j<num; j++){

                    sb.append('.');

                }

                sb.append('Q');

                for(int j=num+1; j<n; j++){

                    sb.append('.');

                }            

                cur.add(sb.toString());

            }

            res.add(new ArrayList<String>(cur));

            return;

        }

        for(int num = 0; num < n; num++){

                queens[index] = num;

                // 如果是有效的，继续搜索

                if(isValid(queens, index)){

                    helper(res, n, index+1, queens);

                }

            }

    }

     private boolean isValid(int[] nqueens, int i){

        for(int idx = 0; idx < i; idx++){

            // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了

            if(nqueens[idx] == nqueens【i】 || Math.abs(nqueens[idx] - nqueens【i】) ==  i - idx){

                return false;

            }

        }

        return true;

    }

}

Palindromepartitioning

public class Solution {

    public List<List<String>> partition(String s) {

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

        helper(s, res, 0, new ArrayList<String>());

        return res;

    }

    private void helper(String s, List<List<String>> res, int index, List<String> cur){

        if(index==s.length()){

            res.add(new ArrayList<String>(cur));

            return;

        }

        for(int i =index; i<s.length(); i++){

            String temp = s.substring(index, i+1);

            if(!isPalindrome(temp))

                continue;

            cur.add(temp);

            helper(s, res, i+1, cur);

            cur.remove(cur.size()-1);

        }

    }

    private boolean isPalindrome(String s){

        int i =0;

        int j = s.length()-1;

        while(i<j){

            if(s.charAt(i) != s.charAt(j))

                return false;

            i++;

            j--;

        }

        return true;

    }

}

Subset II

public class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

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

        boolean[] visited = new boolean[nums.length];

        helper(nums, res, 0, new ArrayList<Integer>(), visited);

        return res;

    }

    private void helper(int[] nums, List<List<Integer>> res, int index, List<Integer> cur, boolean[] visited){

        res.add(new ArrayList<Integer>(cur));

        for(int i =index;i<nums.length; i++){

            if(visited【i】 ||i>0 &&nums【i】==nums[i-1]&&!visited[i-1])

                continue;

            visited【i】 = true;

            cur.add(nums【i】);

            helper(nums, res, i+1, cur, visited);

            visited【i】 = false;

            cur.remove(cur.size()-1);

        }

    }

}

Restore IP address

public class Solution {

    public List<String> restoreIpAddresses(String s) {

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

        helper(res,s, "", 0, 0);

        return res;

    }

    private void helper(List<String> res, String s, String cur, int i, int count){

        if(count>4){

            return;

        }

        if(count==4 && i == s.length()){

            res.add(cur.substring(1, cur.length()));

        }

        for(int j=1; j<=3; j++){

            count++;

            if(i+j>s.length()) break;

            String sub = s.substring(i, i+j);

            if(j>1 && s.charAt(i) =='0') break;

            if(Integer.valueOf(sub)>255) break;

            cur = cur+ "." + sub;  

            helper(res, s, cur, i+j, count);

            count--;

            cur = cur.substring(0, cur.length()-sub.length()-1);

        }

    }

}

如果爱

感谢carybabywin分享~~~

潘蜜拉

感谢carybabywin分享~~~