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, tmp = board[r][c]; -> board[r][c] = '#'; -> board[r][c] = tmp;

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

• 0047. Permutations II

• 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

• 0040. Combination Sum II

• 0077. Combinations

• 0078. Subsets

• 0090. Subsets II

These are more of a DP:

• 0377. Combination Sum IV (This is more of a permutation where you can use an element repeatedly.)

• 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

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/