# Backtracking

## Key points:

* Use cases:
  * Output all results. This must be backtracking, at most with memorization.
  * Find how many ways to do xyz. DP, a typical DFS + memorization pattern.
* One important idea of Backtracking is `modify -> restore`, like this one is different from traditional `add, remove` List: [`212. Word Search II`](https://leetcode.com/problems/word-search-ii/description/), `tmp = board[r][c]; -> board[r][c] = '#'; -> board[r][c] = tmp;`

![](https://upload.wikimedia.org/wikipedia/commons/1/1f/Eight-queens-animation.gif)

## Permutation

* Duplicate: 1) sort array/list first; 2) skip duplicate at each level by `if (visiting[i] || i > 0 && nums[i] == nums[i-1] && !visiting[i-1]) continue;`
* Have a `boolean[] visiting` to marked points visited, avoid duplicate
* [0046. Permutations](https://jaywin.gitbook.io/leetcode/solutions/0046-permutations)
* [0047. Permutations II](https://jaywin.gitbook.io/leetcode/solutions/0047-permutations-ii)
* [0060. Permutation Sequence](https://jaywin.gitbook.io/leetcode/solutions/0060-permutation-sequence)

## Combination / Subset

* Duplicate: 1) sort array/list first; 2) skip duplicate at each level by `if (i > start && candidates[i] == candidates[i-1]) continue;`
* Don't need to have visited set or boolean array
* [0039. Combination Sum](https://jaywin.gitbook.io/leetcode/solutions/0039-combination-sum)
* [0040. Combination Sum II](https://jaywin.gitbook.io/leetcode/solutions/0040-combination-sum-ii)
* [0077. Combinations](https://jaywin.gitbook.io/leetcode/solutions/0077-combinations)
* [0078. Subsets](https://jaywin.gitbook.io/leetcode/solutions/0078-subsets)
* [0090. Subsets II](https://jaywin.gitbook.io/leetcode/solutions/0090-subsets-ii)

These are more of a DP:

* [0377. Combination Sum IV](https://jaywin.gitbook.io/leetcode/solutions/0377-combination-sum-iv) (This is more of a permutation where you can use an element repeatedly.)
* [0518. Coin Change 2](https://jaywin.gitbook.io/leetcode/solutions/0518-coin-change-2)

<https://leetcode.com/problems/partition-equal-subset-sum> <https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/>

## Template

<https://discuss.leetcode.com/topic/46161/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning>

```java
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> tmpres = new ArrayList<Integer>();
        backtrack(candidates, 0, target, tmpres, res);
        return res;
    }

    private void backtrack(int[] candidates, 
                           int start, 
                           int remain,
                           List<Integer> tmpres,
                           List<List<Integer>> res) {
        if (remain < 0) return;
        if (remain == 0) {
            res.add(new ArrayList<Integer>(tmpres));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            tmpres.add(candidates[i]);
            backtrack(candidates, i, remain-candidates[i], tmpres, res);
            tmpres.remove(tmpres.size()-1);
        }
    }
}
```

## Another type of backtracking

one common type is add -> remove. the other type is like drawing a tree, enumerate possible solutions <https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/> <https://leetcode.com/problems/generate-parentheses/description/> <https://leetcode.com/problems/gray-code/description/>

## Find all results

<https://leetcode.com/problems/palindrome-partitioning/description/>