This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
Recommended reading
- CSDN home page
- GitHub open source address
- Unity3D plugin sharing
- Jane’s address book
- My personal blog
- QQ group: 1040082875
Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.
A, the title
1. Algorithm topic
“Given an array of non-repeating positive integers and positive integers, find all the numbers in the array and the combination of the given positive integers.”
Title link:
Source: LeetCode
Link: 39. Combination Summation – LeetCode (leetcode-cn.com)
2
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]]Copy the code
Example 2: input: candidates =,3,5 [2], target = 8 output: [,2,2,2 [2], filling [2], [3, 5]]Copy the code
Second, the problem solving
1. Analysis of ideas
For this kind of problem to find all possible solutions, we can try to use the method class of search backtracking.
Using a recursive function, enumerating all combinations, the recursion terminates when the target value is 0 or the array runs out.
2. Code implementation
Code reference:
public class Solution {
public IList<IList<int>> CombinationSum(int[] candidates, int target)
{
List<IList<int>> result=new List<IList<int> > (); List<int> current=new List<int> (); dfs(candidates,target,result,current,0);
return result;
}
public void dfs(int[] candidates, int target, List<IList<int>> result, List<int> current,int begin)
{
if (target == 0)
{
result.Add(new List<int>(current));
return;
}
if (target < 0) return;
for (inti = begin; i < candidates.Length; i++) { current.Add(candidates[i]); target -= candidates[i]; dfs(candidates, target, result, current,i); target += candidates[i]; current.Remove(candidates[i]); }}}Copy the code
3. Time complexity
Time complexity: O(S)
Where S is the sum of the lengths of all feasible solutions.
Space complexity: O(Target)
The spatial complexity is not the same as the stack depth of the recursion, in the worst case, the recursive O(target) layer.
Third, summary
This is a classic example of backtracking, and of course pruning optimization.