# 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

##


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding.bea.ai/coding-patterns-and-template/4.-backtracking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.