This article originated from personal public account: TechFlow, original is not easy, for attention


Today is the 20th article in the LeetCode series on number composition.

describe

Given a candidate set of type int and a target of type int, return all combinations of numbers such that the sum of all the numbers in the combination equals target.

Note:

  1. All the entries are positive
  2. None of the elements are duplicated
  3. There can be no repetition of the answer
  4. Each element can be used several times

Sample 1:

Input: candidates = [2,3,6,7], target = 7, A solution set is: [[7], [2,2,3]Copy the code

Example 2:

Input: candidates = [2,3, 2], target = 8, A solution set is: [[2,2,2,2], [3,5]Copy the code

Answer key

We get this problem or in accordance with the old rules to think about the solution of violence, but after a careful thought, we will find that there seems to be no clue, the reason for no clue is also very simple, because of a condition in the problem: an element can be used several times at will.

We simply don’t know how many times an element can be used, which makes our enumeration of violence feel like a lost cause. It’s a lot easier to get rid of this condition, because each element only has two states left, either to take or not to take, and we can write it as a binary number. This leads to a common way of representing states, binary notation.

Binary representation

For example, if we have three numbers, and each of them has two states to choose from or not to choose from, and we want to enumerate all the states of the three numbers, what should we do?

We can of course do this recursively, making decisions at each level of recursion whether or not to select the current element, recurse separately. But instead of doing that, we can simplify the process with binary. This principle is very simple, we all know that in the computer binary, each binary bit has only two states, 0 or 1, so we use 1 to represent take, 0 means not to take, so the three states of take or not to take actually correspond to a binary number. The 3-bit binary, the corresponding numbers are 0 to 7, which means we just need to traverse 0 to 7 to get all the states of the 3 bits.

Let’s say that the number we’re walking through right now is 5, and the binary representation of 5 is 101, and then we’re going to take 1 and 0 and we’re going to take 0 and we’re going to take 0. So 5 corresponds to the state where the first and the third take, and the second one doesn’t. We can do this very easily with bit operations. So for example, if we want to determine if we took the ith bit, we can use (1 << I), << means to move to the left, so to move to the left is the same thing as multiplying by 2,If you move n to the left, that’s the same thing as multiplying by 2 to the n. 1 corresponds to the 0th bit from the right, which is the lowest binary bit, and we shift it by I to the left and we multiply itSo you get the ith bit. So once we’ve got it, we just have to put it in binary with stateWith the operationAnd you can figure out whether the ith bit in state is 0 or 1.

Because in binary, and evaluates each digit of two numbers with an and, the result is a binary number. Since the number we use for the operation of and is (1 << I), only the ith bit of it is 1, so the result of the operation of and on other bits must be 0. After the operation of and with state, if the result is greater than 0, it means that the ith bit of state is also 1; otherwise, it is 0. So we get the i-th bit of state.

Since bitwise operations are instruction set operations, they can be computed faster than addition, subtraction, multiplication and division in some languages without instruction set optimization. In addition to fast, its biggest advantage is to save space and convenient calculation, these two advantages are actually one, we say one by one.

First, to save space, with binary representation, we can use a 32-bit int to represent all the states of 0 and 1 for 32 objects. If we store in arrays, we obviously need an array of length 32, which requires a lot more space. This is not obvious in a single state, but becomes significant once the data volume is large. Especially in dense I/O, the lighter the data, the more efficient the transmission.

The second advantage is that it’s easy to compute, and the reason why it’s easy to compute is that if you’re going to iterate over all the states, if you’re going to iterate over arrays or other data structures, you’re going to have to iterate recursively, and that’s going to be very cumbersome. It’s convenient to use binary, because binary represents the states of all elements 0 and 1, so we just loop through an integer range. As in the example above, we need to enumerate the states of three elements, we just need to iterate from 0 to 7. If we have multiple elements, that’s fine, if we have N elements, we just iterate from 0 to (1 << N) minus 1.

But there’s still a problem, you might say if we use int for states, we can only represent 32 items at most, but what if there’s more? One way is to use INT64, which is a larger int. If a larger int still doesn’t solve the problem, it doesn’t matter. There are also third-party packages that implement the same principle. But let’s be honest, we rarely have more than 64 items for us to enumerate, because that number is so large that it’s almost endless.

Back to the question

I’m sure you’re familiar with how binary notation works and how it works, but in this case you can have multiple elements, and binary notation doesn’t seem to work, so how do we solve this problem? Is such a large space for nothing?

Of course it’s not for nothing, but there are ways to deal with this. And it’s pretty simple, because they say that all of the entries are positive, so for each of the entries, we’re going to take a finite number of entries. For example, in the example [2, 3, 6, 7] target is 7. For element 2, target is 7. So we can expand the candidate set, we can expand one 2 into three, and we can continue to expand three, so that the candidate set looks like this: [2, 2, 2, 3, 3, 6, 7], and we can use binary representation.

But obviously this method does not work, because if there is a 1 in the data, and the target is slightly larger, it must be gg, obviously the complexity will explode. So this is a method that works in theory, but it doesn’t work in practice, and I’m presenting it purely to introduce binary notation.

Search for everything

When a problem obviously has many situations to traverse, but it is difficult for us to traverse directly, it is often a search problem, we can think about whether we can use the method of search problem to solve.

This problem is already very obvious, the search conditions have been, the search space is also understood, the rest is to develop a search strategy.

I personally think that the search strategy is actually the search order and scope, the appropriate search order and scope can greatly reduce the complexity of coding and calculation, and then interspersing with appropriate pruning, can be very beautiful to complete a search problem.

So let’s look at this problem with a little bit of thought, and if we write this problem backwards, the code isn’t really that complicated. It’s easy to write:

def dfs(x, sequence, candidates, target):

    if x == target:

        ans.append(sequence)

        return

    

    for i in candidates:

        if x + i > target:

            continue

        sequence.append(i)

        dfs(x+i, sequence, candidates, target)

        sequence.pop()

Copy the code

You see it’s just a couple of lines, we’re going through one number at a time adding to the current sum x and recursing down, and we’re also adding pruning of the present and the judgment. If the current and have exceeded target, then it is obviously no longer possible to form a positive solution, so we will skip ahead.

But as we’ve all seen, in the code above, the range we search for is all the candidates, and we don’t put any restrictions on those candidates. This actually hides a big problem, remember one of the instructions of the question is that there should be no repetition of the answer. In other words, different orders of the same elements are considered to be the same solution, and we need to subtract them. For example, [3, 2, 2] and [2, 2, 3] are considered duplicates, but in the above search strategy, we do nothing to control this situation, which results in the need to redo after all the answers are found. Finding answers that contain duplicates and then de-duplicating them obviously consumes a lot of computing resources, so this simple search strategy is far from the best.

Let’s analyze the problem first. When does duplication happen?

I think you can all see that when we get out of order. Let’s say we have two numbers, 3 and 4, and if we choose 3 and then 4, that’s the same thing as choosing 4 and then 3. If we don’t put any restrictions on the choices of 3 and 4, then there will be duplication. In other words, if we order the choices of 3 and 4, we can avoid repetition. If there is no repetition in the first place, there is no need to repeat, which can save a lot of time.

So what we need to do is determine the order in which the elements are selected when searching, and limit the search to avoid repetition. The way it works in the code is when we enumerate the candidate set, we didn’t do anything before, we now have to artificially restrict it, we can only select the element after the previously selected element, we can only take it back and not forward. So we need to pass in a subscript in the DFS to mark the largest subscript that we have taken before. We can only take the one after this subscript, so that the search has order and avoids the problem of element duplication and complexity.

With that in mind, the rest of the code is simple.

class Solution:

    def dfs(self, ret, pos, sequence, now, target, candidates):

        if now == target:

            # add answer, need.copy()

            ret.append(sequence.copy())

            return 

        

        for i in range(pos, len(candidates)):

            # If too large, no recursion

            if now + candidates[i] > target:

                continue

            Store the sequence recursively

            sequence.append(candidates[i])

            self.dfs(ret, i, sequence, now+candidates[i], target, candidates)

            sequence.pop()

            

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        ret = []

        self.dfs(ret, 0[],0, target, candidates)

        return ret

Copy the code

From a code point of view, we didn’t change much, and all the details were pretty much in the search and traverse boundaries and control conditions. Compared to the overall algorithm and code logic, these are the least important things, but they are the real thing to solve the problem.

Deformation of the title

Today’s problem has a variation, which is LeetCode number 40. Most of the questions have the same meaning, except for two changes. Number one, in question 40, we removed elements from the candidate set and there is no restriction on repetition, and number two, we no longer allow elements to be reused. Everything else is consistent with this problem.

And if we think about it, if we get rid of the condition for repetition, and it doesn’t seem to be changing, can we just change the condition for recursion a little bit? Before, we started from pos position and then iterated. Now, since it cannot be repeated, the pos that we took before cannot be retrieved again. Shall we just change the for loop to start from POS +1?

This is certainly possible if there are no duplicates in the elements of the candidate set. But unfortunately, this condition has also been removed. So the candidate set itself is likely to repeat itself, and if you follow the same pattern you’ll get repeated answers.

For example, if the candidate set is [1, 2, 3, 2, 2] and target is 5, we will find two [2, 3] in the answer. Even though we only used each element once, we still violated the restriction that the answer should not be repeated.

You might have a lot of ideas, like manual de-weighting, like we could manipulate the number of elements to de-weight duplicate elements. Unfortunately, neither is optimal. The first way is of course feasible. It is a very simple idea to find all feasible solutions and then repeat them. Through optimization, the complexity problem can be solved. The second idea is not feasible, because if we remove duplicate elements, some solutions may be lost. For example, [1, 2, 2], also sum is equal to 5, but if we get rid of the repeated 2, then we can’t get this solution.

To solve the problem, let’s go back to the search strategy. Manually sifting and processing data is just a weird technique to use when you have to. The search strategy is the core of the problem.

The first is that we need to find all the solutions, which means we can’t delete the elements. The second is that we want to search for results that are not repeated. It seems paradoxical, is it possible that we want to avoid repetition, but also that repeating elements can occur?

If you think about it, you’ll find it’s possible. But from a search strategy perspective, it’s hard to think of. The first thing we need to do is keep the elements clustered, which means that the same elements should be clustered together. And to do that, it’s really easy. We just sort. It’s not hard to think of a reason for doing this: to avoid duplication. If the data is scattered, it’s hard for us to duplicate it. Again, using the previous example, when we recurse from 2, we can find the solution [2, 3]. When we recurse from 3, we can still find the solution [3, 2]. Although we restrict the order of traversal strictly from front to back, our restriction is ineffective because the elements are scattered. To keep the restrictions in place, we need to sort and aggregate the same elements so that each search is actually a number greater than or equal to the current element, which ensures that there is no duplication.

The candidate set is [2, 2, 2, 3, 4] and target is 7. Obviously [2, 2, 3] is the answer, but how can we guarantee that [2, 2, 3] occurs only once? Because we have three twos, but to pick two twos, we need a mechanism so that only one answer will be found. You can’t do that with strategy. You have to prune. We could certainly introduce additional data structures to solve the problem, but it would be more troublesome, and there is a simpler way to do it.

If I > pos+1 and the candidates[I] == candidates[i-1], then skip. Pos is the last choice of location, at the start of a recursive, into the 1, I think this condition should be everybody can see, but why it may be confused about effectively, translated into vernacular, this condition is actually the limit point: when there are multiple elements appear same, must choose the subscript small, also is in front of me.

Let’s examine the conditions that can trigger a continue. There are only two cases, the first:

   idx:                 pos pos+1 pos+2 pos+3(i)

   candidates:          1   2     2     2  

Copy the code

Where pos is the number we picked last time, let’s say it’s 1, and our current position is pos+3. As you can see from the figure above, pos+1 to pos+3 are all equal. If we want to select pos+3 and skip pos+1 and pos+2, the continue will skip. The reason is very simple, because we already chose pos and POS +1 in the previous recursion, so if we chose pos and pos+3, it would definitely constitute repetition. That is, we guarantee that enumerations of successive elements must start at the first.

Another situation is similar:

   idx:                 pos pos+1 pos+2 pos+3(i)

   candidates:          2   2     2     2  

Copy the code

So we’re going to skip pos+1 and pos+2 and go to pos+3 and continue because we’re enumerating two twos. We didn’t do pos and pos+1 in the previous recursion. Now we want to skip pos+1 and pos+2 and get pos+3 directly. The corresponding cases are the same, so we need to skip.

We solved the problem by combining sorting with the pruning method above, and if you look at it closely, you’ll see that the two methods complement each other. Neither method alone works, but working together makes it very easy to solve the problem. With these two points in mind, the code is pretty simple:

class Solution:

    

    def dfs(self, ret, sequence, now, pos, target, candidates):

        if now == target:

            ret.append(sequence.copy())

            return

        

        for i in range(pos+1, len(candidates)):

            cur = now + candidates[i]

            # pruning

            # If there are multiple elements of the same type, ensure that the first one goes first

            if cur > target or (i > pos+1 and candidates[i] == candidates[i- 1) :

                continue

            sequence.append(candidates[i])

            self.dfs(ret, sequence, cur, i, target, candidates)

            sequence.pop()

            

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        # sort to ensure that the same elements are placed together

        candidates = sorted(candidates)

        ret = []

        self.dfs(ret, [], 0.- 1, target, candidates)

        return ret

Copy the code

Don’t know if you have felt the search strategy and pruning from the varieties of power and clever, I also like the topic of today, if you can put two topics read today, I think you understanding of the depth first search and backtracking algorithm can more on a step, this is also I will introduce these two issues together. Tomorrow in LeetCode, we’ll look at LeetCode problem 41 and look for the first natural number that doesn’t appear.

This is the end of today’s article. If you feel that you have gained something, please pay attention to it. Your contribution is very important to me.

This article is formatted using MDNICE