Backtracking

78. Subsets

Standard backtracking

T: O(2 ^ n) For every index i two recursive case originates, So Time Complexity is O(2^n). There are 2 ^ n subsets to generate.

S: O(n) The space complexity can be reduced if the output array is not stored and the static and global variable is used to store the output string.

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        dfs(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void dfs(int[] nums, int startIndex, List<Integer> curt, List<List<Integer>> result) {
        result.add(new ArrayList<>(curt));
        for (int i = startIndex; i < nums.length; i++) {
            curt.add(nums[i]);
            dfs(nums, i + 1, curt, result);
            curt.remove(curt.size() - 1);
        }
    }

90. Subsets II

Sort array and add code below to skip over duplicates:

if (i > currentIndex && nums[i] == nums[i - 1]) {
     continue;
}

39. Combination Sum

Typical backtracking template.

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    dfs(0, new ArrayList<>(), res, candidates, target);
    return res;
}

private void dfs(int startIndex,
                 List<Integer> curtList, 
                 List<List<Integer>> result, 
                 int[] candidates, 
                 int target) {
    if (target == 0) {
        result.add(new ArrayList<>(curtList));
        return;
    }
    for (int i = startIndex; i < candidates.length; i++) {
        if (target - candidates[i] < 0) continue;
        curtList.add(candidates[i]);
        dfs(i, curtList, result, candidates, target - candidates[i]);
        curtList.remove(curtList.size() - 1);
    }
}

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    res = []
    cur = []
    candidates.sort
    self.helper(candidates,0,cur,res,0,target)
    return res


def helper(self, candidates,start_index, cur, res,sum,target):
    if sum == target:
        res.append(copy.deepcopy(cur))
    for i in range(start_index,len(candidates)):
        if sum +candidates[i] > target:
            continue

Remove duplicate by checking the last element is the same as current element. For example. [1, 1, 5, 6] only output one result [1, 5, 6]. Use if (i > startIndex && candidates[i] == candidates[i - 1]) continue; to remove duplicate.

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(0, new ArrayList<>(), res, candidates, target);
        return res;
    }
    
    private void dfs(int startIndex,
                     List<Integer> curtList, 
                     List<List<Integer>> result, 
                     int[] candidates, 
                     int target) {
        if (target == 0) {
            result.add(new ArrayList<>(curtList));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (i > startIndex && candidates[i] == candidates[i - 1]) continue;
            if (target - candidates[i] < 0) continue;
            curtList.add(candidates[i]);
            dfs(i + 1, curtList, result, candidates, target - candidates[i]);
            curtList.remove(curtList.size() - 1);
        }
    }

216. Combination Sum III

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(new ArrayList<>(), 1, n, k, res);
    return res;
}

private void dfs(List<Integer> curt, int start, int n, int k, List<List<Integer>> res) {
    if (n == 0 && curt.size() == k) {
        res.add(new ArrayList<>(curt));
        return;
    }
    for (int i = start; i <= 9; i++) {
        if (n - i < 0 || curt.size() >= k) {
            continue;
        }
        curt.add(i);
        dfs(curt, i + 1, n - i, k, res);
        curt.remove(curt.size() - 1);
    }
}

377. Combination Sum IV

To get the number of combinations sums to target. DFS Reduce each number on each level, if the target reach 0, it means there is 1 combination. Summarize the combinations of each level and return. Use memo to store sum : count relationship.

public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    return dfs(nums, target, new HashMap<>());
}

private int dfs(int[] nums, int target, Map<Integer, Integer> memo) {
    if (memo.containsKey(target)) {
        return memo.get(target);
    }
    if (target == 0) {
        return 1;
    }
    int count = 0;
    for (int n : nums) {
        if (target - n < 0) {
            continue;
        }
        count += dfs(nums, target - n, memo);
    }
    memo.put(target, count);
    return count;
}

def combinationSum4(self, nums: List[int], target: int) -> int:
    dic = {}
    return self.dfs(nums, target, dic)
    
def dfs(self, nums, target, dic):
    if target in dic:
        return dic[target]
    if target == 0:
        return 1
    count = 0
    for n in nums:
        if target - n < 0:
            continue
        count += self.dfs(nums, target - n, dic)
    dic[target] = count
    return count

46. Permutations

Backtracking starting from 0 on each level. Use a boolean array to check if this element has been visited.

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

private void dfs(int[] nums, 
                 List<Integer> curtList, 
                 boolean[] visited,
                 List<List<Integer>> result) {
    if (curtList.size() == nums.length) {
        result.add(new ArrayList<>(curtList));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        curtList.add(nums[i]);
        dfs(nums, curtList, visited, result);
        curtList.remove(curtList.size() - 1);
        visited[i] = false;
    }
}

def permute(self, nums: List[int]) -> List[List[int]]:
    bool_array = [False]*len(nums)
    result =[]
    self.helper(nums,[], result, bool_array)
    return result 

def helper(self, nums, curr, result,bool_array):
    if curr and len(curr)==len(nums):
        result.append(copy.deepcopy(curr))
    for i in range(len(nums)):
        if bool_array[i]==False:
            curr.append(nums[i])
            bool_array[i] = True

47. Permutations II

Sort array. Also remove duplicate when the current element equals previous element, and the previous element is visited ().

if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])) {
    continue;
}

55. Jump Game

T: O(2^n) proof

    public boolean canJump(int[] nums) {
        return dfs(nums, 0);
    }
    
    private boolean dfs(int[] nums, int index) {
        if (index >= nums.length - 1) {
            return true;
        }
        for (int i = 1; i <= nums[index]; i++) {
            if (dfs(nums, index + i)) {
                return true;
            }
        }
        return false;
    }

491. Increasing Subsequences

The array is not sorted. For example, [4, 6, 7, 5, 7], you don't add

[4,6]

[4,6,7]

and [4,6,7]

but need add [4, 6, 7, 7]. It requires to remove duplicate on each layer by use a set.

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void dfs(int[] nums, 
                     int startIndex, 
                     List<Integer> list,
                     List<List<Integer>> res) {
        if (list.size() >= 2) {
            res.add(new ArrayList<>(list));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (set.contains(nums[i])) continue;
            if (list.isEmpty() || nums[i] >= list.get(list.size() - 1)) {
                set.add(nums[i]);
                list.add(nums[i]);
                dfs(nums, i + 1, list, res);
                list.remove(list.size() - 1);
            }
        }
    }

113. Path Sum II

End the traversal when reach leaf node. Add root.left != null and root.right != null condition to traversal to guarantee no null node is reached.

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        helper(root, sum, new ArrayList<>(), result);
        return result;
    }
    
    private void helper(TreeNode root,
                        int sum,
                        List<Integer> curtList, 
                        List<List<Integer>> res) {
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                curtList.add(root.val);
                res.add(new ArrayList<>(curtList));
                curtList.remove(curtList.size() - 1);
            }
            return;
        }
        curtList.add(root.val);
        if (root.left != null) helper(root.left, sum - root.val, curtList, res);
        if (root.right != null) helper(root.right, sum - root.val, curtList, res);
        curtList.remove(curtList.size() - 1);
    }

254. Factor Combinations

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<Integer>(), n, 2);
        return res;
    }
    
    public void dfs(List<List<Integer>> res, ArrayList<Integer> temp, int n, int s) {
        if (n <= 1) {
            if (temp.size() > 1) {
                res.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        for (int i = s; i <= n; i++) {
            if (n % i == 0) {
                temp.add(i);
                dfs(res, temp, n / i, i);
                temp.remove(temp.size()-1);
            }
        }
    }

    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (n <= 1) return res;
        dfs(res, new ArrayList<>(), 2, n);
        return res;
    }
    
    private void dfs(List<List<Integer>> res, List<Integer> curt, int index, int n) {
        for (int i = index; i * i <= n; i++) {
            if (n % i != 0) continue;
            curt.add(i);
            curt.add(n / i);
            res.add(new ArrayList<>(curt));
            curt.remove(curt.size() - 1);
            dfs(res, curt, i, n / i);
            curt.remove(curt.size() - 1);
        }
    }

def getFactors(self, n: int) -> List[List[int]]:
    res = []
    self.dfs(2, n, [], res)
    return res

def dfs(self, startindex, n, curt, res):
    if n == 1 and len(curt) > 1:
        res.append(copy.deepcopy(curt))
        return
    for i in range(startindex, n + 1):
        if n % i == 0:
            self.dfs(i, n // i, curt + [i], res)

494. Target Sum

DFS Backtracking all path.

T: O(2 ^ n)

    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        helper(nums, 0, 0, S);
        return count;
    }
    
    private void helper(int[] nums, int index, int sum, int target) {
        if (index == nums.length) {
            if (sum == target) count++;
            return;
        }
        helper(nums, index + 1, sum + nums[index], target);
        helper(nums, index + 1, sum - nums[index], target);
    }

Add memorization. O(n * S)

    public int findTargetSumWays(int[] nums, int S) {
        int[][] memo = new int[nums.length][2001];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return helper(nums, 0, 0, S, memo);
    }
    
    private int helper(int[] nums, int index, int sum, int target, int[][] memo) {
        if (index == nums.length) {
            return (sum == target) ? 1 : 0;
        }
        if (memo[index][sum + 1000] != -1) {
            return memo[index][sum + 1000];
        }
        memo[index][sum + 1000] = helper(nums, index + 1, sum + nums[index], target, memo) 
                                + helper(nums, index + 1, sum - nums[index], target, memo);
        return memo[index][sum + 1000]; 
    }

22. Generate Parentheses

Backtracking to generate parentheses as well as maintain balances of the brackets. Append "(" and left + 1, bal + 1, or append ")" and right + 1, bal - 1.

When bal < 0 it means any invalid solution such as "))((". When bal == 0 and sb.length() == n * 2 it means it is a valid solution.

T: O(2 ^ n) (actually it is 4^n / sqrt(n)) S: 4^n / sqrt(n)

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if (n == 0) return list;
        dfs(n, new StringBuilder(), 0, 0, 0, list);
        return list;
    }
    
    private void dfs(int n, 
                     StringBuilder sb, 
                     int left, 
                     int right, 
                     int bal, List<String> list) {
        if (bal < 0) return;
        if (sb.length() == n * 2) {
            if (left == right && left == n && bal == 0) {
                list.add(sb.toString());
            }
            return;
        }
        int len = sb.length();
        sb.append('(');
        dfs(n, sb, left + 1, right, bal + 1, list);
        sb.setLength(len);
        sb.append(')');
        dfs(n, sb, left, right + 1, bal - 1, list);
        sb.setLength(len);
    }

def generateParenthesis(self, n: int) -> List[str]:
    res = []
    self.dfs(0, 0, 0, n, "", res)
    return res

def dfs(self, left, right, bal, n, s, res):
    if bal < 0:
        return
    if len(s) == n * 2:
        if left == n and right == n and bal == 0:
            res.append(s)
        return
    self.dfs(left + 1, right, bal + 1, n, s + "(", res)
    self.dfs(left, right + 1, bal - 1, n, s + ")", res)

301. Remove Invalid Parentheses

Count the number of left brackets and right brackets when need to make a balance. Backtracking to get the string when left == 0 and right == 0 and balance == 0.

public List<String> removeInvalidParentheses(String s) {
    Set<String> set = new HashSet<>();
    int left = 0, right = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') left++;
        else if (c == ')') {
            if (left > 0) left--;
            else right++;
        }
    }
    dfs(s.toCharArray(), 0, new StringBuilder(), left, right, 0, set);
    return new ArrayList<>(set);
}

private void dfs(char[] chars, 
                 int i, 
                 StringBuilder sb, 
                 int left, 
                 int right, 
                 int bal, 
                 Set<String> set) {
    if (left < 0 || right < 0 || bal < 0) return;
    if (i == chars.length) {
        if (left == 0 && right == 0 && bal == 0) set.add(sb.toString());
        return;
    }
    int len = sb.length();
    if (chars[i] == '(') {
        dfs(chars, i + 1, sb, left - 1, right, bal, set);
        dfs(chars, i + 1, sb.append("("), left, right, bal + 1, set);
    } else if (chars[i] == ')') {
        dfs(chars, i + 1, sb, left, right - 1, bal, set);
        dfs(chars, i + 1, sb.append(")"), left, right, bal - 1, set);
    } else {
        dfs(chars, i + 1, sb.append(chars[i]), left, right, bal, set);
    }
    sb.setLength(len);
}

797. All Paths From Source to Target

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
					
    path.add(0);
    dfsSearch(graph, 0, res, path);
					
    return res;
}

private void dfsSearch(int[][] graph, int node, List<List<Integer>> res, List<Integer> path) {
    if (node == graph.length - 1) {
        res.add(new ArrayList<Integer>(path));
        return;
    }

    for (int nextNode : graph[node]) {
        path.add(nextNode);
        dfsSearch(graph, nextNode, res, path);
        path.remove(path.size() - 1);
    }
}

90. k Sum II (LintCode)

    public List<List<Integer>> kSumII(int[] nums, int k, int target) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0 || nums.length < k) {
            return res;
        }
        Arrays.sort(nums);
        dfs(nums, k, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] nums,
        int k,
        int target,
        int startIndex,
        List<Integer> curt,
        List<List<Integer>> res) {
        if (target == 0 && curt.size() == k) {
            res.add(new ArrayList<>(curt));
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (target - nums[i] < 0 || curt.size() >= k) {
                continue;
            }
            curt.add(nums[i]);
            target -= nums[i];
            dfs(nums, k, target, i + 1, curt, res);
            target += nums[i];
            curt.remove(curt.size() - 1);
        }
    }

17. Letter Combinations of a Phone Number

T: O(3^n + 4^ m) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input. S: T: O(3^n + 4^ m)

Map<Integer, List<String>> map = new HashMap<>();
public List<String> letterCombinations(String digits) {
    map.put(2,  Arrays.asList("a", "b", "c"));
    map.put(3,  Arrays.asList("d", "e", "f"));
    map.put(4,  Arrays.asList("g", "h", "i"));
    map.put(5,  Arrays.asList("j", "k", "l"));
    map.put(6,  Arrays.asList("m", "n", "o"));
    map.put(7,  Arrays.asList("p", "q", "r", "s"));
    map.put(8,  Arrays.asList("t", "u", "v"));
    map.put(9,  Arrays.asList("w", "x", "y", "z"));
    List<String> result = new ArrayList<>();
    if (digits == null || digits.isEmpty()) return result;
    dfs(digits, 0, new StringBuilder(), result);
    return result;
}

private void dfs(String digits, int index, StringBuilder sb, List<String> res) {
    if (index == digits.length()) {
        res.add(sb.toString());
        return;
    }
    for (String c : map.get(digits.charAt(index) - '0')) {
        sb.append(c);
        dfs(digits, index + 1, sb, res);
        sb.setLength(sb.length() - 1);
    }
}

698. Partition to K Equal Sum Subsets

Backtracking until find answer. Be careful with the number of groups found.

public boolean canPartitionKSubsets(int[] nums, int k) {
    int n = nums.length;
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % k != 0) {
        return false;
    }
    return dfs(nums, 0, 0, sum / k, new boolean[n], 0, k);
}

private boolean dfs(int[] nums, int index, int sum, int target, boolean[] used, int useItem, int k) {
    if (k == 1) {
        return true;
    }
    if (sum == target && useItem > 0) {
        return dfs(nums, 0, 0, target, used, useItem, k - 1);
    }
    for (int i = index; i < nums.length; i++) {
        if (used[i] || sum + nums[i] > target) continue;
        used[i] = true;
        if (dfs(nums, i + 1, sum + nums[i], target, used, useItem + 1, k)) {
            return true;
        }
        used[i] = false;
    }
    return false;
}

def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    n = len(nums)
    sum = 0
    for num in nums:
        sum += num
    if sum % k != 0:
        return False
    used = [False for i in range(n)]
    return self.dfs(nums, 0, 0, int(sum / k), 0, k, used)
    
def dfs(self, nums, index, curtsum, target, useItems, k, used):
    if k == 1:
        return True
    if curtsum == target and useItems > 0:
        return self.dfs(nums, 0, 0, target, useItems, k - 1, used)
    for i in range(index, len(nums)):
        if used[i] or curtsum + nums[i] > target:
            continue
        used[i] = True
        if self.dfs(nums, i + 1, curtsum + nums[i], target, useItems + 1, k, used):
            return True
        used[i] = False
    return False

241. Different Ways to Add Parentheses

Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
    if (map.containsKey(input)) return map.get(input);
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < input.length(); i++) {
        if ("+-*".indexOf(input.charAt(i)) != -1) {
            String left = input.substring(0, i);
            String right = input.substring(i + 1);
            List<Integer> leftList = diffWaysToCompute(left);
            List<Integer> rightList = diffWaysToCompute(right);
            for (int l : leftList) {
                for (int r : rightList) {
                    char c = input.charAt(i);
                    switch (c) {
                        case '+' : list.add(l + r);
                            break;
                        case '-' : list.add(l - r);
                            break;
                        case '*' : list.add(l * r);
                            break;
                    }
                }
            }
        }
    }
    if (list.size() == 0) list.add(Integer.valueOf(input));
    map.put(input, list);
    return list;
}

465. Optimal Account Balancing

Create a map to calculate all balance of each person. Store all non-zero balance to a list to do backtracking.

Start the backtracking from 0 position, set the list.get(pos) as curt value, find the next balance between pos + 1 and array length, check if next and curt are opposite sign (curt * next < 0).

Set the list(i) as curt + next then keep the traversal from pos + 1.

When see list.get(pos) == 0, means it can traverse from pos + 1.

    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> balance = new HashMap<>();
        for (int[] t : transactions) {
            balance.putIfAbsent(t[0], 0);
            balance.putIfAbsent(t[1], 0);
            balance.put(t[0], balance.get(t[0]) + t[2]);
            balance.put(t[1], balance.get(t[1]) - t[2]);
        }
        List<Integer> list = new ArrayList<>();
        for (int key : balance.keySet()) {
            if (balance.get(key) != 0) list.add(balance.get(key));
        }
        return dfs(list, 0);
    }
    
    private int dfs(List<Integer> list, int index) {
        if (index == list.size()) return 0;
        int curt = list.get(index);
        if (curt == 0) {
            return dfs(list, index + 1);
        }
        int min = Integer.MAX_VALUE;
        for (int i = index + 1; i < list.size(); i++) {
            int next = list.get(i);
            if (curt * next < 0) {
                list.set(i, curt + next);
                min = Math.min(min, dfs(list, index + 1) + 1);
                list.set(i, next);
            }
            if (next == -curt) break;
        }
        return min;
    }

51. N-Queens

Start from row 0, only fill col and cross diag on each spot. When row reach n, output a valid result. The cross diagonal coordinates are calculated by:

int cross1 = row + j;
int cross2 = row - j + n - 1;

int n;
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    this.n = n;
    char[][] grid = new char[n][n];
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = '.';
        }
    }
    boolean[] col = new boolean[n];
    boolean[] diag = new boolean[2 * n - 1];
    boolean[] diag2 = new boolean[2 * n - 1];
    dfs(0, col, diag, diag2, grid, res);
    return res;
}

private void dfs(int x, boolean[] col, boolean[] diag, boolean[] diag2, char[][] grid, List<List<String>> res) {
    if (x == n) {
        List<String> toAdd = new ArrayList<>();
        for (int i = 0; i < n; i ++) {
            toAdd.add(String.valueOf(grid[i]));
        }
        res.add(toAdd);
        return;
    }
    for (int j = 0; j < n; j++) {
        int dval = x - j + n - 1;
        int adval = x - (n - 1 - j) + n - 1;
        if (col[j] || diag[dval] || diag2[adval]) continue;
        col[j] = true;
        diag[x + n - j - 1] = true;
        diag2[x + j] = true;
        grid[x][j] = 'Q';
        dfs(x + 1, col, diag, diag2, grid, res);
        grid[x][j] = '.';
        diag2[x + j] = false;
        diag[x + n - j - 1] = false;
        col[j] = false;
    }
}

489. Robot Room Cleaner

Traverse the entire floor and detect if it is visited and movable. The direction is base on the sum of previous direction and the delta. turnRight to the next direction and ndir = (dir + k) % 4 . Also step back after the current dfs is completed.

Robot robot;
Set<Integer> visited = new HashSet<>();
int[][] dirs = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};
public void cleanRoom(Robot robot) {
    this.robot = robot;
    dfs(0, 0, 0);
}

private void dfs(int x, int y, int dir) {
    robot.clean();
    visited.add(x * 10000 + y);
    for (int k = 0; k < 4; k++) {
        int ndir = (dir + k) % 4;
        int nx = x + dirs[ndir][0];
        int ny = y + dirs[ndir][1];
        if (!visited.contains(nx * 10000 + ny) && robot.move()) {
            dfs(nx, ny, ndir);
            stepBack();
        }
        robot.turnRight();
    }
}

private void stepBack() {
    robot.turnRight();
    robot.turnRight();
    robot.move();
    robot.turnRight();
    robot.turnRight();
}

291. Word Pattern II

Cut the pattern and str, backtracking to detect if any pattern would move forward. Use a set to detect the cut has been visited.

public boolean wordPatternMatch(String pattern, String str) {
    Map<Character, String> map = new HashMap<>();
    return dfs(pattern.toCharArray(), 0, str, 0, map, new HashSet<>());
}

private boolean dfs(char[] arr, int index, String s, int i, Map<Character, String> map, Set<String> set) {
    if (index == arr.length && i == s.length()) {
        return true;
    }
    if (index == arr.length || i == s.length()) {
        return false;
    }
    char c = arr[index];
    if (map.containsKey(c)) {
        String curt = map.get(c);
        if (!s.substring(i).startsWith(curt)) return false;
        return dfs(arr, index + 1, s, i + curt.length(), map, set);
    }
    for (int k = i; k < s.length(); k++) {
        String cut = s.substring(i, k + 1);
        if (set.contains(cut)) continue;
        map.put(c, cut);
        set.add(cut);
        if (dfs(arr, index + 1, s, k + 1, map, set)) {
            return true;
        }
        map.remove(c);
        set.remove(cut);
    }
    return false;
}

753. Cracking the Safe

Use a StringBuilder to append the digits to crack the safe, also use visited set to keep track of all combinations. Add unique combinations as well as reach the passcode size equals to k^n.

public String crackSafe(int n, int k) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) sb.append('0');
    int targetSize = (int)Math.pow(k, n);
    Set<String> visited = new HashSet<>();
    visited.add(sb.toString());
    dfs(n, k, sb, visited, targetSize);
    return sb.toString();
}

private boolean dfs(int n, int k, StringBuilder sb,
                   Set<String> visited, int targetSize) {
    if (visited.size() == targetSize) return true;
    String curt = sb.substring(sb.length() - n + 1);
    for (int i = 0; i < k; i++) {
        String next = curt + String.valueOf(i);
        if (visited.contains(next)) continue;
        visited.add(next);
        sb.append(i);
        if (dfs(n, k, sb, visited, targetSize)) {
            return true;
        } else {
            sb.deleteCharAt(sb.length() - 1);
            visited.remove(next);
        }
    }
    return false;
}

351. Android Unlock Patterns

This question asks to get all number of patterns from number of keys from m to n. Backtracking to sum up all numbers from starting point 1 to 9, also the remain combinations are between m to n.

Create a skip matrix to determine if the number need to be skipped. For example, between 1 to 3 is 2, it needs skip or visited. Use a boolean array to determine if a number is visited.

public int numberOfPatterns(int m, int n) {
    int[][] skip = new int[10][10];
    skip[1][3] = skip[3][1] = 2;
    skip[1][7] = skip[7][1] = 4;
    skip[3][9] = skip[9][3] = 6;
    skip[7][9] = skip[9][7] = 8;
    skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] 
        = skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5;
    boolean[] used = new boolean[10];
    int res = 0;
    for (int k = m; k <= n; k++) {
        for (int start = 1; start <= 9; start++) {
            res += dfs(k - 1, used, skip, start);
        }
    }
    return res;
}

private int dfs(int remain, boolean[] used, int[][] skip, int curt) {
    if (remain < 0) return 0;
    if (remain == 0) return 1;
    used[curt] = true;
    int res = 0;
    for (int next = 1; next <= 9; next++) {
        if (!used[next] && (skip[curt][next] == 0 || used[skip[curt][next]])) {
            res += dfs(remain - 1, used, skip, next);
        }
    }
    used[curt] = false;
    return res;
}

There is a way to eliminate the path. The combination starting from 1 is the same as starting from 3,7,9, also starting from 2 is the same as starting from 4,6,8. Which gives:

    int res = 0;
    for (int i = m; i <= n; i++) {
        res += dfs(i - 1, used, skip, 1) * 4;
        res += dfs(i - 1, used, skip, 2) * 4;
        res += dfs(i - 1, used, skip, 5);
    }
    return res;

1240. Tiling a Rectangle with the Fewest Squares

Go through every point in the rectangle, starting from (0,0), (0,1), ..., (n, m).
If rect[r,..., r+k][c, ..., c+k] is an available area, then cover a k*k square starting at point (r,c).
Try every possible size of square k * k, where k = min(n-r, m-c).
Optimzation: If cnt >= ans, then stop.

int res = Integer.MAX_VALUE;
public int tilingRectangle(int n, int m) {
    dfs(0, 0, new boolean[m][n], 0);
    return res;
}

private void dfs(int r, int c, boolean[][] rect, int count) {
    int n = rect.length, m = rect[0].length;
    if (count >= res) return;
    if (r >= n) {
        res = count;
        return;
    }
    if (c >= m) {
        dfs(r + 1, 0, rect, count);
        return;
    }
    if (rect[r][c]) {
        dfs(r, c + 1, rect, count);
        return;
    }
    for (int k = Math.min(n - r, m - c); k >= 1 && isValid(rect, r, c, k); k--) {
        cover(rect, r, c, k);
        dfs(r, c + 1, rect, count + 1);
        uncover(rect, r, c, k);
    }
}

private boolean isValid(boolean[][] rect, int r, int c, int k) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (rect[r + i][c + j]) return false;
        }
    }
    return true;
}

private void cover(boolean[][] rect, int r, int c, int k) {
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            rect[r+i][c+j] = true;
        }
    }
}

private void uncover(boolean[][] rect, int r, int c, int k) {
    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            rect[r+i][c+j] = false;
        }
    }
}

2101. Detonate the Maximum Bombs

function maximumDetonation(bombs: number[][]): number {
  const n = bombs.length;
  let maxDetonated = 1;

  function canDetonate(bomb1: number[], bomb2: number[]): boolean {
    const [x1, y1, r1] = bomb1;
    const [x2, y2] = bomb2;
    const dx = x1 - x2;
    const dy = y1 - y2;
    return dx * dx + dy * dy <= r1 * r1;
  }

  function dfs(start: number, visited: boolean[]): number {
    let count = 1;
    visited[start] = true;

    for (let i = 0; i < n; i++) {
      if (!visited[i] && canDetonate(bombs[start], bombs[i])) {
        count += dfs(i, visited);
      }
    }
    return count;
  }

  for (let i = 0; i < n; i++) {
    const visited = new Array(n).fill(false);
    const detonated = dfs(i, visited);
    maxDetonated = Math.max(maxDetonated, detonated);
  }

  return maxDetonated;
}

1239. Maximum Length of a Concatenated String with Unique Characters

class Solution {
public:
    int maxLength(vector<string>& arr) {
        return dfs(arr, 0, "");
    }

private:
    int dfs(vector<string>& arr, int index, string current) {
        if (!isUnique(current)) {
            return 0;
        }
        int maxLen = current.size();
        for (int i = index; i < arr.size(); ++i) {
            maxLen = max(maxLen, dfs(arr, i + 1, current + arr[i])); 
        }
        return maxLen;
    }

    bool isUnique(const string& s) {
        vector<bool> seen(26, false);
        for (char c : s) {
            if (seen[c - 'a']) return false;
            seen[c - 'a'] = true;
        }
        return true;
    }
};

PreviousDFS on String NextDFS+Memo

Last updated 6 months ago

Was this helpful?

hashtag90. k Sum IIarrow-up-right (LintCode)

hashtag1240. Tiling a Rectangle with the Fewest Squares

90. k Sum II (LintCode)

1240. Tiling a Rectangle with the Fewest Squares