This is the 27th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Today’s topic

Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and 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 =,1,2,7,6,1,5 [10], target = 8, output: [,1,6 [1],,2,5 [1], [1, 7], [2, 6]]

Example 2:

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

Tip:

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

Train of thought

The difference between this problem and the sum of combinations 1 is:

  • 1. Each element can no longer be used indefinitely, but only once, so the subscript of each recursion can no longer start with the current subscript, but with I +1.
  • 2. The element has duplicate elements, so it needs to be de-duplicated.

Both of the above two points have the effect of de-duplication. One is to ensure that there are no duplicate elements in the results, and the other is to ensure that there are no duplicate searches in the horizontal traversal. Other than that, like most backtracking.

Recursively through the number group, each time first judge whether the current subscript element is the same as the previous element, if the same judgment at the same time whether the previous element is in use, if not, directly skip, because the previous element has been traversed before.

Then check whether the current element is less than or equal to target. If it is greater than target, it means that the difference between target and the current element must be less than 0. Otherwise, break the loop. Because the element following this element must be greater than or equal to the current element, the target minus the difference must also be less than zero, so skip ahead. This is a very important pruning operation.

Add the current element to the path list, and set the current VIS [I] to true to indicate access.

Enter the recursion and determine if target is 0. If it is 0, add to the list of answers.

To recurse, you need to backtrack, remove the current element from the path list, and set access to false.

Summed up in two questions:

  • 1. How to ensure that each number is used only once in each combination? Answer: Each recursive call to a method starts with the next number of the current number
  • 2. How to ensure that the solution set cannot contain repeated combinations? A: In an ordered array, if the number at index I is equal to the number at index I-1, we skip I and go to the next loop

Again, use the following framework code:

Result = [] backtrack(path, select list):ifEnd conditions are met: result.add(path)return

forSelect in Select list: Make select backtrack(path, select list) unselectCopy the code

Code implementation:

List<List<Integer>> result = new LinkedList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<Integer> list = new ArrayList<>();
    Arrays.sort(candidates);
    combinationList(candidates, 0, target, list);
    return result;
}

public void combinationList(int[] candidates, int start, int target, List<Integer> list{
    if (target == 0) {
        result.add(new ArrayList<>(list));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        // Clipping case one
        if (target - candidates[i] < 0) {
            break;
        }
        // Clipping case two
        if (i > start && candidates[i] == candidates[i - 1]) {
            continue;
        }
        list.add(candidates[i]);
        // This is I +1, because the element is not reusable. When you use start+1, it causes double counting
        combinationList(candidates, i + 1, target - candidates[i], list);
        / / backlist.removeLast(); }}Copy the code

Execution time: 2 ms, beating 99.32% of all Java commits

Memory consumption: 38.4 MB, beating 85.81% of users in all Java commits

summary

All of the problems solved by backtracking algorithm have similar purposes. They are all problems that are looking for all feasible solutions. We can try to solve them by searching backtracking. At the same time, remember the basic framework of algorithm implementation, can greatly reduce the difficulty of implementation.