4ms java solution


  • 1
    L
    public class Solution {
    List<List<Integer>> results=new ArrayList<List<Integer>>();
    boolean flag=false;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates==null||candidates.length==0) return results;
        Arrays.sort(candidates);
        int[] counts=new int[candidates.length];
        dfs(candidates,target,0,counts);
        return results;
    }
    public void dfs(int[] candidates,int target,int begin,int[] counts){
        if(target==0){
            flag=true;
            return;
        }
        for(int i=begin;i<candidates.length&&candidates[i]<=target;i++){
            for(int n=1;n*candidates[i]<=target;n++){
                counts[i]=n;
                dfs(candidates,target-n*candidates[i],i+1,counts);
                if(flag){
                    List<Integer> result=new ArrayList<>();
                    for(int m=0;m<=i;m++){
                        for(int j=0;j<counts[m];j++){
                            result.add(candidates[m]);
                        }
                    }
                    results.add(result);
                    flag=false;
                }
            }
            counts[i]=0;
        }
    }
    

    }


  • 0
    W

    very good. You can remove the gloabal variables like this:

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            if (candidates == null || candidates.length == 0) {
                return results;
            }
            Arrays.sort(candidates);
            int[] counts = new int[candidates.length];
            dfs(candidates, target, 0, counts, results);
            return results;
        }
    
        public boolean dfs(int[] candidates, int target, int begin, int[] counts, List<List<Integer>> results) {
            if (target == 0) {
                return true;
            }
            for (int i = begin; i < candidates.length && candidates[i] <= target; i++) {
                for (int n = 1; n * candidates[i] <= target; n++) {
                    counts[i] = n;
                    if (dfs(candidates, target - n * candidates[i], i + 1, counts, results)) {
                        List<Integer> result = new ArrayList<>();
                        for (int m = 0; m <= i; m++) {
                            for (int j = 0; j < counts[m]; j++) {
                                result.add(candidates[m]);
                            }
                        }
                        results.add(result);
                    }
                }
                counts[i] = 0;
            }
            return false;
        } 

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.