给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被

亦凉 2023-08-17 16:28 106阅读 0赞

运用回溯

package program;
    
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @Auther: 大哥的叔
     * @Date: 2019/9/28 15:05
     * @Description:刚开始想的是用整数划分将所有结果存储然后再和原数组匹配但是后面的思路没了
     * 然后就看人家用回溯解似乎也行
     */
    public class Shuzizuhe {
        //首先是创建一list的全局变量作为返回值
        List<List<Integer>> lists = new ArrayList<>();
        private int []candidates;
        private int len;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            //判断是否符合组合数组的要求不符合直接返回
            int len = candidates.length;
            if (candidates == null||len==0||target<0){
                return lists;
            }
            //对要用的数组排序可以简单降低复杂度
            Arrays.sort(candidates);
          this.len =len;
          this.candidates =candidates;
          findshuzuzuhe(target,0,new Stack<>());
            return lists;
        }
    
        /**
         *
         * @param target 要形成组合的数
         * @param start 开始判断的位置
         * @param p 存放值
         */
        private void  findshuzuzuhe(int target, int start, Stack<Integer> p){
            if(target == 0){
                //将值存入
                lists.add(new ArrayList<>(p));
                return;
            }
            for (int i = start; i <len && target-candidates[i]>=0 ; i++) {
                p.add(candidates[i]);
                findshuzuzuhe(target-candidates[i],i,p);
                p.pop();
            }
        }
    
        public static void main(String[] args) {
            int[] candidates = {2, 3, 6, 7};
            int target = 7;
           Shuzizuhe shuzizuhe = new Shuzizuhe();
            List<List<Integer>> combinationSum = shuzizuhe.combinationSum(candidates, target);
            System.out.println(combinationSum);
        }
    }