LeetCode - The Backtrack Part

The backtrack is use to get all information of one path.

Permutations and Combinations are the typical backtrack problems.

Here’s the template:

void backtrack(int start, List<Integer> path, List<List<Integer>> res, int[] arr){
    // if reach the target, add the path into result and return
    if (start == arr.length){
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i< arr.length; i++){
        // add new item in path
        path.add(arr[i]);

        // backtrack recursion
        backtrack(i+1, path, res, arr);

        // remove the added item
        path.remove(path.size() - 1);
    }
}

For Permutation and Combination problems, the answer should not contains duplicates, and we can use this template to reduce the duplicates answer.

    void backtrack(List<List<Integer>> res, List<Integer> list, int start, int[] nums){
        res.add(new ArrayList<>(list));
        
        if (start == nums.length){
            return;
        }
        
        for (int i = start; i< nums.length; i++){
            list.add(nums[i]);
            backtrack(res, list, i+1, nums);
            list.remove(list.size() - 1);
            
            // make sure no duplicates in res.
            while(i + 1 < nums.length && nums[i] == nums[i + 1]){
                i++;
            }
        }
    }

For some specific problem, we need to find a better way to backtrack so that we can reduce the time complexity.

• N Queens

• Sudoku Solver