Location>code7788 >text

LeetCode40.Combinatorial Sums II

Popularity：912 ℃/2024-08-14 21:25:12

LeetCode40.Combinatorial Sums II

Power Button Title Link (opens new window)

Given an array of candidates and a target, find all combinations of candidates that sum to the target.

Each number in candidates can only be used once in each combination.

Description: All numbers (including the target number) are positive integers. The solution set cannot contain duplicate combinations.

  • Example 1.
  • inputs: candidates = [10,1,2,7,6,1,5], target = 8,
  • The set of solutions sought is.
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  • Example 2.
  • Inputs: candidates = [2,5,2,1,2], target = 5,
  • The set of solutions sought is.
[
  [1,2,2],
  [5]
]

reasoning

This topic and [LeetCode39. combinatorial sums - Tomorrowland_D - Blogland ()]() The following distinction is made:

  1. Each number in the candidates of this question can be used only once in each combination.
  2. The elements of the array candidates in this question are duplicated, while [LeetCode39. combinatorial sums - Tomorrowland_D - Blogland ()]() is the array candidates with no duplicate elements

Finally this question and [LeetCode39. combinatorial sums - Tomorrowland_D - Blogland ()]() requires the same, but the solution set cannot contain duplicate combinations.

The difficulty with this question is in distinction 2: sets (arrayscandidates) have duplicate elements, but not yet duplicate combinations。

  • Intuitively, we can think of the following approach: I'll solve for all the combinations, and then use set or map to de-emphasize them, and it's easy to timeout doing so!

  • So remove duplicate combinations right in the search process.

  • Why is this de-emphasis so hard to understand.By de-duplication, it actually means that used elements cannot be selected repeatedly. It seems so simple when you put it that way!

  • We all know that combinatorial problems can be abstracted into a tree structure, so "used" has two dimensions on this tree structure, one dimension is used on the same branch, and the other dimension is used on the same tree level.Failure to understand these two levels of "used" is the root cause of the lack of thorough understanding of de-duplication.

  • So the question is, do we want it to have been used on the same tree level or on the same branch?

  • Looking back at the topic, elements can be duplicated within the same combination, it's fine how they are duplicated, but two combinations can't be the same.

  • So what we want to de-emphasize are the "used" ones on the same tree level, and the ones on the same branch are all elements in a combination, so we don't need to de-emphasize them.。

  • To understand de-duplication let's take an example where candidates = [1, 1, 2], target = 3, (for convenience candidates are already ordered)

Emphasize that the array needs to be sorted for tree-level de-duplication!

40.组合总和II

1. Parameters for recursion

  • As with the Leetcode39 combination, you need result to hold the result and path to hold a single path
  • sum to hold all the current sums
  • startindex to mark the current traversal position.
  • A USED array is also needed for de-duplication, which will be highlighted below!!!!

2. End conditions for recursion

  • As in the previous question, we return when sum >= targetSum, and if it is equal, we collect the result

3. Logic of single-level search

The biggest difference here from LeetCode39. combined sums is that they are de-emphasized.

We mentioned earlier: to de-emphasize the "same tree level used", how to determine the same tree level elements (the same element) is used or not.

in the event thatcandidates[i] == candidates[i - 1] besidesused[i - 1] == false, which means: the previous branch, which used candidates[i - 1], i.e. the same tree level has used candidates[i - 1]。

At this point, the for loop should do the continue operation.

This piece is more abstract, as shown:

40.组合总和II1

I've labeled the change in USED in orange in the graph, as you can see in the case where candidates[i] == candidates[i - 1] is the same:

  • used[i - 1] == true, indicating that the same branch candidates[i - 1] is used

  • used[i - 1] == false, indicating that the same tree level candidates[i - 1] is used

  • Why is used[i - 1] == false the same tree level? Because it is the same tree level, and used[i - 1] == false means that the currently fetched candidates[i] are backtracked from candidates[i - 1].

  • And used[i - 1] == true, indicating that it's going to the next level of recursion, to the next number, so it's on the tree branch, as shown here

The code for single level recursion is as follows:

for (int i = startIndex; i < () && sum + candidates[i] <= target; i++) {
    // used[i - 1] == true, indicating that the same branch candidates[i - 1] was used
    // used[i - 1] == false, indicating that the same tree level candidates[i - 1] was used
    // To skip elements that are used at the same tree level
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue; }
    }
    sum += candidates[i];
    path.push_back(candidates[i]); used[i] = true; }
    used[i] = true;
    backtracking(candidates, target, sum, i + 1, used); // Difference 1 from 39. sum of combinations: here it's i + 1, and each number can only be used once in each combination
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}

Code:

class Solution {
public.
vector<int> path; vector<vector<int> > result;
vector<vector<int> > result;
void backtracking(vector<int> candidates, int targetSum, int sum, int startindex, vector<bool> & used) {
if (sum >= targetSum) {
if (sum == targetSum) result.push_back(path);
return;
}
// The pruning process here is covered in Combined Sums!
for (int i = startindex; i < () && sum + candidates[i]<=targetSum; i++) {
// De-weight if it's the same element in the same layer! That is, skip the current loop
            // used[i - 1] == true, indicating that the same tree branch candidates[i - 1] was used
            // used[i - 1] == false, same tree level used by candidates[i - 1].
            // To skip elements that are used at the same tree level
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue;
sum += candidates[i];
path.push_back(candidates[i]); used[i] = 1; && used[i - 1] == 0
used[i] = 1;
// Note that this is i+1, and unlike the sum of combinations explained earlier, you can't pick duplicate elements here.
backtracking(candidates, targetSum, sum, i + 1, used);
sum -= candidates[i];
path.pop_back();
// backtracking sets the previously used element to 0, signaling that it's an element at the same level (tree level), not on a branch
used[i] = 0;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
(); ();
if (() == 0) return result.
vector<bool> used((), 0);
//Note that it must be sorted here
sort((), ());
backtracking(candidates, target, 0, 0, used);
return result.
}
};

Attention:

  • The author is also quoted several times in this articleCode Randomizer The original picture of the original author, if you want to go deeper, you can follow the original author and read the original author's article! [Code Randomizer ()]()
<Previous Next>