Combined sum leetcode

---

title: Combinatorial summation -Leetcode
date: 2022-04-19 09:47:00
tags: Make a little progress every day

---

Daily topic

subject ： Combinatorial summation

To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can press In any order Return these combinations .

candidates Medium The same Numbers can Unlimited repeat selected . If the selected number of at least one number is different , Then the two combinations are different .

For a given input , Guarantee and for target The number of different combinations of is less than 150 individual .

Example ：

Example 1：

Input ：candidates = [2,3,6,7], target = 7
Output ：[[2,2,3],[7]]
explain ：
2 and 3 Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful 2 You can use it multiple times .
7 Is also a candidate , 7 = 7 .
Only these two combinations .

Example 2：

Input : candidates = [2,3,5], target = 8
Output : [[2,2,2,2],[2,3,3],[3,5]]

Example 3：

Input : candidates = [2], target = 1
Output : []

Tips ：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate Every element in is Different from each other
1 <= target <= 500

Code ：

class Solution {    public List<List<Integer>> combinationSum(int[] candidates, int target) {        List<List<Integer>> res =  new ArrayList<>();        // If the array is empty , Directly return empty results         if(candidates==null||candidates.length==0){            return res;        }        // Prioritize         Arrays.sort(candidates);        //dfs        dfs(candidates,target,0,new ArrayList<>(),res);        return res;    }    public void dfs(int[] candidates,int target ,int start,List<Integer> list,List<List<Integer>> res){        // If the target value is 0, Indicates that a combination has been found , Add to result set         if(target==0){            res.add(new ArrayList<>(list));            return;        }        // Traversal array         for (int i = start; i < candidates.length; i++) {            // If the current value is greater than the target value , You don't need to continue traversing             if(candidates[i]>target){                return;            }            list.add(candidates[i]);            // Update target value and starting position             dfs(candidates,target-candidates[i],i,list,res);            // to flash back , Delete current value             list.remove(list.size()-1);        }    }}

Daily words

The above is the sum of the combinations -Leetcode The whole content of

Copyright notice ：
Original Blogger ： Cowherd Conan
Personal blog links ：https://www.keafmd.top/

If it helps you , Thank you for clicking on == One key, three links == Support ！
[ ha-ha ][ Huai Quan ]

come on. ！

Joint efforts ！

Keafmd

You can see it here , You know the following , Let's make progress together ！