LeetCode Topic Backtracking

Overview

backtracking

• if the current solution is suitable, then add the answer; backtrack (go back) and check for other solutions
• if the current solution is not suitable, then eliminate that and backtrack (go back) and check for other solutions

78. Subsets

https://leetcode.com/problems/subsets/

Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

very basic backtracking

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, nums, 0, new ArrayList<Integer>());
        return res;
    }
    
    void dfs(List<List<Integer>> res, int[] nums, int start, List<Integer> curr)  {
        // bottom case
        res.add(new ArrayList<Integer>(curr));
        
        for (int end = start; end < nums.length; end++) {
            curr.add(nums[end]);
            dfs(res, nums, end + 1, curr);
            curr.remove(curr.size() - 1);
        }
    } 
}

class Solution {
public:
    
    int n;
    vector<int> path;
    vector<vector<int>> ans;
    
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        
        dfs(nums, 0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums, int start) {
        ans.push_back(path);
        for (int i = start; i < n; i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};

• Time complexity: $\mathcal{O}(N \times 2^N)$ to generate all subsets and then copy them into output list

• Space complexity: $\mathcal{O}(N)$ to maintain curr, and are modifying curr in-place with backtracking; output array can be ignored

Bit Manipulation

3 numbers: 0~7
000 {}
001 {1}
010 {2}
011 {1, 2}
100 {3}
101 {1, 3}
110 {2, 3}
111 {1, 2, 3}

n numbers: 0 ~ 2^n - 1

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        for (int i = 0; i < 1 << nums.size(); i++) {
            vector<int> now;
            for (int j = 0; j < nums.size(); j++)
                if (i >> j & 1)
                    now.push_back(nums[j]);
            res.push_back(now);
        }
        return res;
    }
};

90. Subsets II +check duplicate

How to check duplicate？(LC217)

• Approach 1：sort, nums[i] != nums[i + 1]

• Approach 2：HashSet or HashMap

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        
        Arrays.sort(nums); // sort
        dfs(res, nums, 0, new ArrayList<Integer>());
        
        return res;
    }
    
    void dfs(List<List<Integer>> res, int[] nums, int start, List<Integer> curr)  {
        res.add(new ArrayList<Integer>(curr));
        
        for (int i = start; i < nums.length; i++) {
            
            if (i != start && nums[i] == nums[i - 1]) continue; // check duplicate
            
            curr.add(nums[i]);
            dfs(res, nums, i + 1, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

131. Palindrome Partitioning

backtracking + isPalindrome

Time: $\mathcal{O}(N \times 2^N)$, where $N$ is the length of the string $s$
Worst case: all the possible substrings are palindrome

• $O(N)$ to generate substring and determine if it is palindrome
• $O(2^N)$ possible substings

Space: $\mathcal{O}(N)$

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        dfs(s, res, new ArrayList<String>(), 0);
        return res;
    }
    void dfs(String s, List<List<String>> res, List<String> curr, int start) {
        // bottom case
        if (start >= s.length()) res.add(new ArrayList<String>(curr));
        
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                // add it to the result list
                curr.add(s.substring(start, end + 1));
                
                // recursion
                dfs(s, res, curr, end + 1);
                
                // remove the last string in curr
                curr.remove(curr.size() - 1);
            }
        }
    }
    
    boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

// backtracking
// using a current list to store palindrome strings
// if curr reaches the length, add it back to the result list
// backtrack: move the last palindrome string and continue dfs

*79. Word Search

https://leetcode.com/problems/word-search/

class Solution{
    public boolean exist(char[][] board, String word) {
        char[] w = word.toCharArray();
        
        // search the cells one by one, if find, return 
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                if (dfs(board, y, x, w, 0)){
                    return true;
                }
            }
        }
        
        return false;
    }

    private boolean dfs(char[][] board, int y, int x, char[] word, int i) {
        // bottom case
        if (i == word.length) return true;
        
        // boundaries
        if (y < 0 || x < 0 || y == board.length || x == board[y].length) return false;
        if (board[y][x] != word[i]) return false;
        
        // mark the cell as completed
        char ch = board[y][x];
        board[y][x] = '#';
        
        boolean exist = dfs(board, y, x+1, word, i+1)
                     || dfs(board, y, x-1, word, i+1)
                     || dfs(board, y+1, x, word, i+1)
                     || dfs(board, y-1, x, word, i+1);
        
        // unmark 
        board[y][x] = ch;
        
        return exist;
    }
}

Time:

$N$: the number of cells, $L$: length of the word to be matched

$$\mathcal{O}(N \cdot 3 ^ L)$$

3 directions to explore (since we won’t go back itself)

Space: $O(N)$

*22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

For the same type of brackets, only the number of left and right brackets needs to be considered

only add a closing parenthesis if closed < open

valid iif open == closed == n

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }
    
    public void backtrack(List<String> res, StringBuilder cur, int open, int close, int max){
        // bottom case
        // valid iif open == closed == n
        if (cur.length() == max * 2) res.add(cur.toString());
        
        // only add open parenthesis if open < n
        if (open < max) {
            cur.append("(");
            backtrack(res, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        // only add a closing parenthesis if closed < open
        if (close < open) {
            cur.append(")");
            backtrack(res, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

time complexity: …

77. Combinations

https://leetcode.com/problems/combinations/
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.

Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(n, k, res, new ArrayList<Integer>(), 0);
        return res;
    }
    void dfs(int n, int k, List<List<Integer>> res, List<Integer> curr, int start) {
        // base
        if (curr.size() == k) res.add(new ArrayList<>(curr));
        
        for (int i = start; i < n; i++) {
            curr.add(i + 1);
            dfs(n, k, res, curr, i + 1);
            curr.remove(curr.size() - 1);
        }
    }
}

class Solution {
public:
    
    vector<vector<int>> ans;
    vector<int> path;
    
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ans;
    }
    
    void dfs(int n, int k, int start) {
        if (!k) {
            ans.push_back(path);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            dfs(n, k - 1, i + 1);
            path.pop_back();
        }
    }
};

Time complexity: $\mathcal{O}(k C_N^k)$

where $C_N^k = \frac{N!}{(N - k)! k!}$ is a number of combinations to build.

Space complexity: $\mathcal{O}(C_N^k)$ to keep all the combinations for an output.

46. Permutation

https://leetcode.com/problems/permutations/
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
public:
    
    int n;
    vector<bool> st; // memo
    vector<vector<int>> ans;
    vector<int> path;
    
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        st = vector<bool>(n);
        
        dfs(nums, 0);
        
        return ans;
    }
    
    void dfs(vector<int>& nums, int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            // backtrack
            if (st[i]) continue;
            st[i] = true;
            path.push_back(nums[i]);
            dfs(nums, u + 1);
            st[i] = false;
            path.pop_back();
            
        }
    }
};

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, res, new ArrayList<Integer>());
        return res;
    }
    
    void dfs(int[] nums, List<List<Integer>> res, List<Integer> curr) {
        if (curr.size() == nums.length) {
            res.add(new ArrayList<>(curr));
            return;
        }

        
        for (int i = 0; i < nums.length; i++) {
            // need duplicate checking!!
            if (curr.contains(nums[i])) continue;
            
            curr.add(nums[i]);
            dfs(nums, res, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

Time complexity: $\mathcal{O}(\sum_{k = 1}^{N}{P(N, k)})$

where $P(N, k) = \frac{N!}{(N - k)!} = N (N - 1) ... (N - k + 1)$ is so-called k-permutations of n

Space complexity: $\mathcal{O}(N!)$
since one has to keep $N!$ solutions