4. Backtracking

Template

void backtrack(int[] candidates, int index, other params, List<Integer> path, List<List<Integer>> result) {
    if (satisfied condition) {
        results.add(new ArrayList<>(path));
    }
    
    for (option in options) {
        //Skip not satified
        if (need filter) {
            continue;
        }
        path.add(option);
        backtrack(candidates, newIndex, path, results);
        path.remove(path.size() - 1);
    }
}

Typic problems

• Permute problem, the time complexity of permute problems is (n! - factorial of n)

//Permute, the input nums don't have duplicates
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, path, results);
    return results;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> results) {
    if (path.size() == nums.length) {
        results.add(new ArrayList<>(path));
        return;
    }
    //Note here for the loop, the start is 0, reference to the permute tree
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, results);
        used[i] = false;
        path.remove(path.size() - 1);
    }
}

//permute on a candidate array that has duplicated numbers
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    Arrays.sort(nums);//注意
    backtrack(nums, used, path, results);
    return results;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> results) {
    if (path.size() == nums.length) {
        results.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        // 如果前面的相邻相等元素没有用过，则跳过
        // 当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, results);
        used[i] = false;
        path.remove(path.size() - 1);
    }
}

• Combination & Subset, where order doesn't matter,

  • the time complexity subset is O(2^n), because for each element, we have two choices: either include it in the subset or exclude it. Since there are n elements, we have 2^n possible combinations of including or excluding each element.

  • For combination of K out of n element, the time complexity is (n!/(k!*(n−k)!)​), This is because, at each step, we have n choices to consider for the next element, but we only need to consider k elements. Hence, the number of recursive calls made is proportional to the number of combinations

//Subsets
// List all subset of the given array, there is not duplicates in the array
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtrack(nums, 0, path, results);
    return results;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> results) {
    if (path.size() > nums.length) {
        return;
    }
    results.add(new ArrayList<>(path));
    //notice i is not from 0, but start, reference to the tree
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, results);
        path.remove(path.size() - 1);
    }
}

// Subset with duplicates
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    //Sort first
    Arrays.sort(nums);
    backtrack(nums, 0, path, results);
    return results;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> results) {
    if (path.size() > nums.length) {
        return;
    }
    results.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        //Skip duplicates
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        path.add(nums[i]);
        backtrack(nums, i + 1, path, results);
        path.remove(path.size() - 1);
    }
}

Combination sum

//Find all the combinations that can sum to the target
//Each element can be used more than once, there is not duplicates
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    backtrack(candidates, 0, target, path, results);
    return results;
}

private void backtrack(int[] candidates, int start, int remain, List<Integer> path, List<List<Integer>> results) {
    if (remain == 0) {
        results.add(new ArrayList<>(path));
        return;
    }
    if (remain < 0) {
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        //注意这次递归是从i开始，而不是i+1，因为同一个element可以用多次
        backtrack(candidates, i, remain - candidates[i], path, results);
        path.remove(path.size() - 1);
    }
}
    
// Combination sum on a unsorted array with duplicated items
// Each item can only be used once, the results shouldn't contain duplicated combinations
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates, 0, target, results, path);
    return results;
}

private void backtrack(int[] candidates, int start, int remain, List<List<Integer>> results, List<Integer> path) {
    if (remain == 0) {
        results.add(new ArrayList<>(path));
        return;
    }
    if (remain < 0) {
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        //Skip duplicated items
        if (i > start && candidates[i] == candidates[i - 1]) {
            continue;
        }
        path.add(candidates[i]);
        //i + 1 makes the same item not be used more than once
        backtrack(candidates, i + 1, remain - candidates[i], results, path);
        path.remove(path.size() - 1);
    }
}

5. DFS