# Backtracking

#### [78. Subsets](https://leetcode.com/problems/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.*

```java
    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](https://leetcode.com/problems/subsets-ii/)

Sort array and add code below to skip over duplicates:

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

#### [39. Combination Sum](https://leetcode.com/problems/combination-sum/)

Typical backtracking template.

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
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
```

{% endtab %}
{% endtabs %}

#### [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)

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.

```java
    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](https://leetcode.com/problems/combination-sum-iii/)

```java
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](https://leetcode.com/problems/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.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
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;
}
```

{% endtab %}

{% tab title="Python" %}

```python
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
```

{% endtab %}
{% endtabs %}

#### [46. Permutations](https://leetcode.com/problems/permutations/)

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

{% tabs %}
{% tab title="Java" %}

```java
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;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
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
```

{% endtab %}
{% endtabs %}

#### [47. Permutations II](https://leetcode.com/problems/permutations-ii/)

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

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

#### [55. Jump Game](https://leetcode.com/problems/jump-game/)

*T: O(2^n)* [*proof*](https://leetcode.com/problems/jump-game/solution/)

```java
    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](https://leetcode.com/problems/increasing-subsequences/)

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

&#x20;   `[4,6]`

&#x20;  `[4,6,7]`

&#x20;  and `[4,6,7]`

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

```java
    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](https://leetcode.com/problems/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.

```java
    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](https://leetcode.com/problems/factor-combinations/)

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Java (Optimized)" %}

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

{% endtab %}

{% tab title="Python" %}

```python
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)
```

{% endtab %}
{% endtabs %}

#### [494. Target Sum](https://leetcode.com/problems/target-sum/)

DFS Backtracking all path.

*T: O(2 ^ n)*

```java
    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)*

```java
    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](https://leetcode.com/problems/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.&#x20;

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

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
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)
```

{% endtab %}
{% endtabs %}

#### [301. Remove Invalid Parentheses](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/problems/all-paths-from-source-to-target/)

```java
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](https://www.lintcode.com/problem/k-sum-ii/description) (LintCode)

![Description](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-ME3fPh9161qUf72wu4b%2F-ME3ijoT0ptcHYdt-9Xb%2FScreen%20Shot%202020-08-06%20at%2010.03.52%20AM.png?alt=media\&token=8a4e3cd2-bb8d-461d-a5d3-8d91c7466c6d)

```java
    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](https://leetcode.com/problems/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)*

```java
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](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/)

Backtracking until find answer. Be careful with the number of groups found.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
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;
}
```

{% endtab %}

{% tab title="Python" %}

```python
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
```

{% endtab %}
{% endtabs %}

#### [241. Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/)

```java
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](https://leetcode.com/problems/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`.&#x20;

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

```java
    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](https://leetcode.com/problems/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;

```java
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](https://leetcode.com/problems/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.&#x20;

```java
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](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/problems/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.

```java
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](https://leetcode.com/problems/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.&#x20;

```java
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:

```java
    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

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

![](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-MLif986IRY_I98pJg5v%2F-MLitY2IDRGUldVjZohM%2Fimage.png?alt=media\&token=1eead616-49c7-4ab4-a423-cea593922953)

```java
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](https://leetcode.com/problems/detonate-the-maximum-bombs/)

```typescript
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](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)

```cpp
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;
    }
};
```