theme: channing-cyan

“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Give an array of positive integer candidates with no repeating elements and a positive integer

Target Finds a unique combination of all the candidates that can be the number and the target number.

The numbers in the candidates can be selected repeatedly without limit. If at least one of the selected numbers has a different number,

The two combinations are unique. For a given input, there are fewer than 150 unique combinations of guaranteed and targets.

 

Example 1: Enter: Candidates = [2,3,6,7], target = 7 Output: [[7],[2,2,3]] Example 2: Enter: candidates = [2,3,5], target = 8 Output: [[2,2,2],[2,3,3],[3,5]] Example 3: Enter: Candidates = [2], target = 1 Output: [] Example 4: Enter: Candidates = [1], target = 1 Output: [[1]] Example 5: Enter: candidates = [1], target = 2 [[1,1]] : 1 <= candidates.length <= 30 1 <= candidates.length [I] <= 200 each element of the candidate is unique. 1 <= target <= 500Copy the code

Source: LeetCode link: leetcode-cn.com/problems/Yg…

Train of thought

  • First of all, according to the meaning and examples, we can see
    • We can use data repeatedly, such as in2,3,5In theTwo, two, two, twoYou can still form numbers8
  • And then we choose to formulate the auxiliary function, because there aretargetLet’s write the exit of the auxiliary function first
    • Export is to release satisfactiontargetfor0Is saved to the result set
    • If the above conditions are not met, it means that to continue traversing the state tree, there are two strategies
    1. The first option is to not pick the numbers in this array,cur + 1So I’m going to go down and I’m not going to do anything
    • That’s where you put inlistIndicates that the current number may be used
    1. The second strategy is to fall back to the previous tree 🌲 node and then to the endlistI want to clear the previous subset state
class Solution {
    public List<List<Integer>> combinationSum(int[] num, int target) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        dfs(num,target,list,res,0);
        
        return res;
    }

    public void dfs(int[] num,int target,LinkedList<Integer> list
    ,List<List<Integer>> res,int cur) {
        if (target == 0) {
            res.add(new LinkedList<>(list));
        }else if (target > 0 && cur < num.length) {
            dfs(num,target,list,res,cur + 1); list.add(num[cur]); dfs(num,target - num[cur],list,res,cur); list.removeLast(); }}}Copy the code