This is the 28th day of my participation in the August Text Challenge.More challenges in August
On Thursday, I was talking to my colleague about swimming crab, and I was craving it. On Saturday, get up early and buy some. I wanted to get up early last Saturday to do the homework, but I didn’t get up later. We can’t cut it off. Let’s do leetcode problem 39 today.
The title
Given an array of positive integer candidates with no duplicate elements and a positive integer target, find all unique combinations of the candidates that can make the sum the target number. The numbers in the candidates can be selected repeatedly without limit. Both combinations are unique if at least one of the selected numbers has a different number. For a given input, there are fewer than 150 unique combinations of guaranteed and targets.
Example 1: input: candidates =,3,6,7 [2], target = 7 output: [[7], [2, 2, 3]]
Example 2: input: candidates =,3,5 [2], target = 8 output: [,2,2,2 [2], filling [2], [3, 5]]
Example 3: Enter: candidates = [2], target = 1 Output: []
Example 4: Enter: candidates = [1], target = 1 Output: [[1]]
Example 5: Input: Candidates = [1], target = 2 Output: [[1,1]]
Train of thought
In fact, it is a backpack problem that needs to be used up exactly, and each item can be used an infinite number of times. Common backpack problems, read cui’s backpack 9 lecture, for beginners, should be very thorough. However, this problem can be solved by deep search + backtracking: For each array from an array, can choose to use or not, if used, because can be repeated use, depth-first traversal, will return to this place, if not, then continue to look at a number, also can choose to use or not, until the use of Numbers and greater than or equal to the target, if just is equal to 1 set of the solution, which is if more than, That’s not a solution, but I don’t have to go through it again. Since the number in the array is guaranteed not to be duplicated, the result must not be duplicated, so there is no need to do a final de-duplication. Of course, the above algorithm has a constant level of small optimization, we can sort the array first, so that when searching, if the sum is greater than n, then we don’t need to iterate, because the sum is definitely greater than target.
Java version code
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { int len = candidates.length; if (len == 0) { return combinationSumList; } combinationSumList = new ArrayList<>(); stack = new Stack<>(); combinationSumDfs(candidates, 0, target); return combinationSumList; } private static List<List<Integer>> combinationSumList = null; private static Stack<Integer> stack = null; private static void combinationSumDfs(int[] candidates, int start, int target) { if (target == 0) { combinationSumList.add(new ArrayList<>(stack)); return; } int len = candidates.length; if (start >= len) { return; } for (int i = start; i < len; i++) { if (candidates[i] <= target) { stack.push(candidates[i]); combinationSumDfs(candidates, i, target - candidates[i]); stack.pop(); }}}}Copy the code