力扣——组合总和

快来打我* 2023-10-02 13:25 3阅读 0赞

##### [组合总和][Link 1] #####

> 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
> 
> candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
> 
> 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

> 输入: candidates = \[2,3,6,7\], target = 7  
> 输出: \[\[7\],\[2,2,3\]\]

示例 2：

> 输入: candidates = \[2,3,5\], target = 8  
> 输出: \[\[2,2,2,2\],\[2,3,3\],\[3,5\]\]

示例 3：

> 输入: candidates = \[2\], target = 1  
> 输出: \[\]

示例 4：

> 输入: candidates = \[1\], target = 1  
> 输出: \[\[1\]\]

示例 5：

> 输入: candidates = \[1\], target = 2  
> 输出: \[\[1,1\]\]

提示：

> 1 <= candidates.length <= 30  
> 1 <= candidates\[i\] <= 200  
> candidate 中的每个元素都是独一无二的。  
> 1 <= target <= 500

class Solution {
        
         public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            Deque<Integer> path = new ArrayDeque<>();
            dfs(candidates, 0, len, target, path, res);
            return res;
        }
    
        /**
         * @param candidates 候选数组
         * @param begin      搜索起点
         * @param len        冗余变量，是 candidates 里的属性，可以不传
         * @param target     每减去一个元素，目标值变小
         * @param path       从根结点到叶子结点的路径，是一个栈
         * @param res        结果集列表
         */
        private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        
            // target 为负数和 0 的时候不再产生新的孩子结点
            if (target < 0) {
        
                return;
            }
            if (target == 0) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            // 重点理解这里从 begin 开始搜索的语意
            for (int i = begin; i < len; i++) {
        
                path.addLast(candidates[i]);
    
                // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
                dfs(candidates, i, len, target - candidates[i], path, res);
    
                // 状态重置
                path.removeLast();
            }
        }
    
    
    }

--------------------

实现调用

package com.kk;
    
    import java.util.*;
    
    //组合总和
    public class CombinationSum {
        
    
        public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            Arrays.sort(candidates);
            Deque<Integer> path = new ArrayDeque<>();
            dfs(candidates, 0, len, target, path, res);
            return res;
        }
    
        private static void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        
            if (target == 0) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = begin; i < len; i++) {
        
                if (target - candidates[i] < 0) {
        
                    break;
                }
    
                path.addLast(candidates[i]);
                System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
    
                dfs(candidates, i, len, target - candidates[i], path, res);
                path.removeLast();
                System.out.println("递归之后 => " + path);
            }
    
        }
    
        public static void main(String[] args) {
        
    
            int[] candidates = new int[]{
        2, 3, 6, 7};
            int target = 7;
            List<List<Integer>> lists = combinationSum(candidates, target);
            System.out.println(Arrays.toString(new List[]{
        lists}));
    
        }
    
    
    
    }

[Link 1]: https://leetcode-cn.com/problems/combination-sum/