BackTracking

重点在于如何构建logic tree

构建logic tree, 方便推算Time complexity https://www.1point3acres.com/bbs/thread-583166-1-1.html

好题

• permutations II

• subset II

• next permutation

• 区分combination-->permutation-->subset不同的出口

• subset是combination的一种

  • combination[1,2,3]和[3,2,1]是一样的，所以需要startIdx来track

  • permutation中[1,2,3]和[3,2,1]不一样，所以always start from 0

• Generate parentheses

• Generalized Abbreviation

• N queens

• Word search ---不能死套模板

Permutation类的题目

• generate all permutations ----> permutations

• next permutation

• generate the permutation number K ----> permutation sequence

Permutations

建立一个visited[] 来记录每个nums[i]是否被用过

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
        if (nums == null ) {
            return res;
        }
        Arrays.sort(nums); //组合类搜索的模板，去重时需要
        boolean[] visited = new boolean[nums.length];
        dfs(res, new ArrayList<Integer>(), nums, visited);
        return res;
    }
    //递归定义：找到所有以permutation开头的排列，加到res里
    private void dfs(List<List<Integer>> res, ArrayList<Integer> permutation, int[] nums, boolean[] visited) {
        //出口
        if(permutation.size() == nums.length) {
            res.add(new ArrayList<Integer>(permutation));
            return;
        }

        //拆解
        for (int i = 0; i < nums.length; i++) {
            if(visited[i]) {
                continue;
            }
            //[1]->[1,2]
            permutation.add(nums[i]);
            visited[i] = true;
            dfs(res, permutation, nums, visited);
            //[1,2] ->[1]
            permutation.remove(permutation.size() - 1);
            visited[i] = false;
            //then next iteration[1]->[1,3]
        }
    }
}

Permutations II

• 去重的题一般都需要先sort array, 然后再check duplicate

• if (i > 0 && nums[i] == nums[i - 1] && !visited[i-1]) continue;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        Arrays.sort(nums); //组合类搜索的模板，去重时需要
        boolean[] visited = new boolean[nums.length];
        dfs(res, new ArrayList<Integer>(), nums, visited);
        return res;
    }

    //递归定义：找到所有以permutation开头的排列，加到res里
    private void dfs(List<List<Integer>> res, ArrayList<Integer> permutation, int[] nums, boolean[] visited) {
        //出口
        if(permutation.size() == nums.length) {
            res.add(new ArrayList<Integer>(permutation));
            return;
        }

        //拆解
        for (int i = 0; i < nums.length; i++) {
            if(visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i-1])) {
                continue;
            }
            //[1]->[1,2]
            permutation.add(nums[i]);
            visited[i] = true;
            dfs(res, permutation, nums, visited);
            //[1,2] ->[1]
            permutation.remove(permutation.size() - 1);
            visited[i] = false;
            //then next iteration[1]->[1,3]
        }
    }
}

Permutation Sequence

• 不适合做面试题

• 康托展开的应用

• 如n=5,x=96时：

  • 首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)

  • 用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.

  • 用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.

  • 用5去除2!得到2余1，类似地，这一位是3.

  • 用1去除1!得到1余0，这一位是2. 最后一位只能是1.

  • 所以这个数是45321. 按以上方法可以得出通用的算法。

public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        boolean[] used = new boolean[n];
        k = k - 1;
        int factor = 1;
        for (int i = 1; i < n; i++) {
            factor *= i; //(n-1) !
        }
        for (int i = 0; i < n; i++) {
            int index = k / factor;
            k = k % factor;
            for (int j = 0; j < n; j++) {
                if (used[j] == false) {
                    if (index == 0) {
                        sb.append(j + 1);
                        used[j] = true;
                        break;
                    } else {
                        index--;
                    }
                }
            }
            if (i < n - 1) {
                factor /= n - 1 - i; 
            }
        }
        return sb.toString();
    }

Combinations

• 给定n和k, 从1~n中选K个数，返回所有结果

class Solution {
    public List<List<Integer>> combine(int n, int k) {
       List<List<Integer>> res = new ArrayList<>();
        if (n == 0 || k == 0 || k > n) {
            return res;
        }
        dfs(res, new ArrayList<Integer>(), n, k, 1);
        return res;
    }

    //递归定义：找到所有以combination开头的组合，加到res里
    private void dfs(List<List<Integer>> res, ArrayList<Integer> combination, int n, int k, int start) {
        //出口
        if(combination.size() == k) {
            res.add(new ArrayList<Integer>(combination));
            return;
        }

        //拆解
        for (int i = start; i <= n; i++) {
            //[1]->[1,2]
            combination.add(i);
            dfs(res, combination, n, k, i + 1);
            //[1,2] ->[1]
            combination.remove(combination.size() - 1);
            //then next iteration[1]->[1,3]
        }
    }
}

Combination Sum组合题

Combination sum I

• no duplicate num

• same num can be chosen unlimited times

• 可选可不选就是for loop to iterate each element as starting index

class Solution {
    //all numbers are positive?
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        helper(res, list, candidates, 0, 0, target);
        return res;
    }
    
    private void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int sum, int target) {
        if (sum > target || start == candidates.length) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(list));
        }
        //可选可不选就是for loop to iterate each element as starting index
        for (int i = start; i < candidates.length; i++) {
            list.add(candidates[i]);
            helper(res, list, candidates, i, sum + candidates[i], target);
            list.remove(list.size() - 1);
        }
    }
}

Combination sum II

• dup num

• each num can only be used once

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] visited = new boolean[candidates.length];
        helper(res, list, candidates, visited, 0, 0, target);
        return res;
    }
    private void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, boolean[] visited, int start, int sum, int target) {
        //return
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(list));
        }
        //iteration
        for (int i = start; i < candidates.length; i++) {
            //check dup
            if (i > 0 && candidates[i-1] == candidates[i] && !visited[i-1]) continue;
            list.add(candidates[i]);
            visited[i] = true;
            helper(res, list, candidates, visited, i + 1, sum + candidates[i], target);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

• Combination sum III

  • 1-9里选K个数sum to N

• Combination Sum IV

  • all positive numbers, no dup

  • find num of combinations that sum to target

  • DP

Subsets II

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums); //组合类搜索的模板，去重时需要
        int[] visited = new int[nums.length];
        dfs(res, new ArrayList<Integer>(), nums, 0, visited);
        return res;
    }
    //递归定义：append all subsets from index idx to the subset,
    private void dfs(List<List<Integer>> res, ArrayList<Integer> subset, int[] nums, int idx, int[] visited) {
        res.add(new ArrayList<Integer>(subset));
        //拆解
        for (int i = idx; i < nums.length; i++) {
            //make sure to visit the duplicate number only when previous has been visited
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
                continue;
            }
            //[1]->[1,2]
            subset.add(nums[i]);
            visited[i] = 1;
            dfs(res, subset, nums, i + 1,visited);
            //[1,2] ->[1]
            subset.remove(subset.size() - 1);
            visited[i] = 0;
            //then next iteration[1]->[1,3]
        }
    }
}

N Queens

• 先想high level的框架，如何能套用dfs模板，不用着急去实现drawBoard()

• 想清楚isValid() logic

• 九章模板清晰好用！

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n < 1) {
            return res;
        }
        List<Integer> cols = new ArrayList<>();
        dfs(res, cols, n);
        return res;
    }

    private void dfs(List<List<String>> res, List<Integer> cols, int n) {
        if (cols.size() == n) {
            res.add(drawBoard(cols));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!isValid(cols, i)) {
                continue;
            }
            cols.add(i);
            dfs(res, cols, n);
            cols.remove(cols.size() - 1);
        }
    }

    private List<String> drawBoard(List<Integer> cols) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cols.size(); j++) {
                if (j == cols.get(i)) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            board.add(sb.toString());
        }
        return board;
    }

    private boolean isValid(List<Integer> cols, int col) {
        int row = cols.size();
        for (int i = 0; i < cols.size(); i++) {
            int j = cols.get(i);
            if (col == j) { //same col
                return false;
            }
            if (j - i == col - row) {//left diagonal
                return false;
            }
            if (j + i == col + row){//right diagonal
                return false;
            } 
        }
        return true;
    }        
}

Word Search

• backtracking必练题

• 需要灵活套用backtracking模板

• 想清楚递归三要素

• 如何定义for loop, 如何定义递归函数

class Solution {
    public boolean exist(char[][] board, String word) {
        if(word == null || word.length() == 0 || board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (isExist(board, visited, i, j, 0, word)) {
                    return true;
                }
            }
        }
        return false;
    }


    private boolean isExist(char[][] board, boolean[][] visited, int i, int j, int pos, String word) {
        //出口
        if (pos == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >=board[0].length || visited[i][j] || board[i][j] != word.charAt(pos)) {
            return false;
        }

        //调用
        visited[i][j] = true;
        //move up
        if (isExist(board, visited, i - 1, j, pos + 1, word)) {
            return true;
        }
        //move down
        if (isExist(board, visited, i + 1, j, pos + 1, word)) {
            return true;
        }
        //move left
        if (isExist(board, visited, i, j - 1, pos + 1, word)) {
            return true;
        }
        //move right
        if (isExist(board, visited, i, j + 1, pos + 1, word)) {
            return true;
        }

        //backtrack
        visited[i][j] = false;
        return false;
    }
}

枚举 Generate Parentheses

• helper(List res, StringBuilder sb, int left, int right, int n)

• left tracks number of '(' has been placed

• right tracks number of ') hash been placed

• when to consider place another '(' --> when left < n

• when to consider place another ')' --> when left > right

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(res, new StringBuilder(), 0, 0, n);
        return res;
    }
    
    private void helper(List<String> res, StringBuilder sb, int left, int right, int n) {
        //return
        if (left == n && right == n) {
            res.add(sb.toString());
            return;
        }
        int len = sb.length();
        //consider add '(' only when left < n
        if (left < n) {
            sb.append('(');
            helper(res, sb, left + 1, right, n);
            sb.setLength(len);
        }
        //consider add ')' only when left > right
        if (left > right) {
            sb.append(')');
            helper(res, sb, left, right + 1, n);
            sb.setLength(len);
        }
    }
}

Generalized Abbreviation

• 典型的backtracking题

• 切记任何时候调用sb.append()完都需要sb.setLength(len), 尤其是递归的出口add result的时候

• 如果是直接res.add(sb.toString()), 没有任何sb.append()操作的话可以 early return

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        helper(res, word.toCharArray(), new StringBuilder(), 0, 0);
        return res;
    }
    private void helper(List<String> res, char[] word, StringBuilder sb, int curNum, int idx) {
        //return
        if (idx == word.length) {
            if (curNum > 0) {
                sb.append(curNum);
            }
            res.add(sb.toString());
            return;
        }
        int len = sb.length();
        //no use char
        helper(res, word, sb, curNum + 1, idx + 1);
        sb.setLength(len);
            
        //use char of word[idx]
        if (curNum > 0) {
            sb.append(curNum);
            sb.append(word[idx]);
            helper(res, word, sb, 0, idx + 1); //reset curNum to 0
        } else {
            sb.append(word[idx]);
            helper(res, word, sb, 0, idx + 1);
        }
        sb.setLength(len);
    }
}