# 4ms java solution

• ``````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++){
}
}
flag=false;
}
}
counts[i]=0;
}
}
``````

}

• 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++) {