Leetcode Back Tracking Problems


Back tracking is the common approach to solve problems about combinations, subsets, permutations or all possible solutions. When asked optimize result or max/min values, we should consider dynamic programming approach first as it usually has better time complexity. The time complexity of back tracking problem are various. For example, Hamiltonian cycle: O(N!), WordBreak: O(2^N) and NQueens: O(N!).

The following code calculate all subsets in a given array, which can be used as a template in many questions.

    public static List<List<Integer>> allCombines(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(),nums, 0);
        return result;

    public static void backtrack(List<List<Integer>> result, List<Integer> tmpList, int[] nums, int index) {
        result.add(new ArrayList<>(tmpList)); //add to result set, usually only when some conditions meet.
        for (int i = index; i < nums.length; i++) { //loop all possible elements for next position.
            tmpList.add(nums[i]); //add.
            backtrack(result, tmpList, nums, i + 1); //back tracking and update parameter.
            tmpList.remove(tmpList.size() - 1); //move back to previous position

Tip: If there are duplicate elements in the array and we want to remove duplicate subsets, need to sort the array first.

        if(i > index && nums[i] == nums[i-1]) continue;

Leetcode 46. Permutations

Leetcode 47. Permutations II

Leetcode 78. Subsets

Leetcode 90. Subsets II

Leetcode 22. Generate Parentheses

Leetcode 301. Remove Invalid Parentheses