> For the complete documentation index, see [llms.txt](https://coding.bea.ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding.bea.ai/coding-patterns-and-template/4.-backtracking.md).

# 4. Backtracking

### Template

```java
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)

<figure><img src="/files/Gy8evChwSrbmXqmCWCeX" alt=""><figcaption></figcaption></figure>

```java
//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,&#x20;
  * 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

<figure><img src="/files/nWgemdB3vgcGg4COdNQN" alt=""><figcaption></figcaption></figure>

```java
//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

```java
//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

##