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);
    }
}

PreviousDFS & Flood-Filling Next7. DP

Last updated 4 years ago

Was this helpful?