“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Topic:

Given a set of numbered candidates and a target number, find all combinations of the candidates that can be summed as target. Each number in the candidates must be used only once in each combination. Note: The solution set cannot contain repeated combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8

[[1,1,6], [1,2,5], [1,7], [2,6]]Copy the code

Example 2:

Input: candidates = [2,5,2,1], target = 5

,2,2 [[1], [5]]Copy the code

Tip:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Problem solving:

According to the order of search, set reasonable variables, in the process of search to determine whether variables appear in the repeated result set. The process of solving the problem is as follows:

1. Sort the data in the array first to facilitate the repeated judgment of the subsequent data. Based on Java language, I can use arrays.sort API to sort the data.

2, Yuan in the loop candidates, add the following arguments and ignore the repeated data options to avoid creating repeated combinations. For example, if [1,2,2,2,5] chooses the first 2, it becomes [1,2]. If you skip it, it’s still [1,2].

if (j > i && candidates[j] == candidates[j- 1] ) {
    continue;
}
Copy the code

3. The currently selected number cannot be repeated with the next selected data. J +1 is passed to the sub-recursion to avoid the current selected j repetition

dfs(candidates, len, j + 1, target - candidates[j], cob, res);
Copy the code

4. If a condition is found, the result will be added to RES and the recursion will be terminated.

if (target == 0) {
    res.add(new ArrayList<>(cob));
    return;
}
Copy the code

The diagram is as follows (combined with the above combing, let’s look at the diagram again) :

Code:

The code is as follows:

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        / / sorting
        Arrays.sort(candidates);

        dfs(candidates, len, 0, target, new ArrayDeque<Integer>(), res);
        return res;
    }

    / * * *@paramCandidates array *@paramLen Array length *@paramI searches * from position I of the candidate array@paramTarget represents the remaining value *@paramCob path from root node to leaf node *@paramRes returns the result */
    private void dfs(int[] candidates, int len, int i, int target,
                     ArrayDeque<Integer> cob, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(cob));
            return;
        }

        for (int j = i; j < len; j++) {
            // Trigger pruning if the value accumulation condition is not met
            if (target - candidates[j] < 0) {
                break;
            }
            // Repeat the node to trigger pruning
            if (j > i && candidates[j] == candidates[j- 1]) {continue;
            }
            cob.addLast(candidates[j]);
            / / recursion
            dfs(candidates, len, j + 1, target - candidates[j], cob, res);
            / / backcob.removeLast(); }}}Copy the code

Space complexity: O(2^n x n) where n is the length of the array candidates. In most recursion + backtracking problems, we cannot give a strict asymptotic compact bound, so only a looser asymptotic upper bound is analyzed here.

Space complexity: O(n), in addition to the array that needs to store the answer, we need O(n) of the list of storage space COB, the array of data that is currently selected in the recursion, and the stack that the recursion needs.

Conclusion:

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. Backtracking is a kind of optimal search method, which searches forward according to the optimal conditions to reach the target. However, when a certain step is explored, it is found that the original choice is not good or fails to reach the target, so it takes a step back to make a new choice. The technology of going back and going again when there is no way is called backtracking method, and the point in a certain state that meets the backtracking condition is called “backtracking point”. Backtracking can be used for many complex, large-scale problems, and has the good name of being a “general solution.”

In this case, the “backtracking” algorithm is used. Because the problem limits the number of repeated solutions in the combination, in fact, this is the condition we prune to reduce the number of backtracking. And if the sum of the accumulations is equal to the expected result that’s the termination condition for backtracking, and also for recursion.

Reference:

  • Leetcode-cn.com/problems/co…
  • baike.baidu.com/item/ backtracking algorithm