# A recursive solution by JAVA

• In fact, the array given does not need to be sorted.

Use a array to record every element's times used for the combination, if times==0, do not add it to a result.

Every time we try to reduce 1 element from the last. When target < 0 or lengh ==0 the recursive can be stopped.

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || candidates.length == 0 || target <= 0)
return res;

// Every number has 0 times initially.
int[] times = new int[candidates.length];
combinationSum(res, candidates, candidates.length, times, target);
return res;
}

private void combinationSum(List<List<Integer>> res, int[] candidates,
int length, int[] times, int target) {
// Get the proper combination.
if (target == 0) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < candidates.length; i++) {
int n = times[i];
while (n-- > 0)
}
return ;
}
// No numbers to use, just stop the recursive.
if (length == 0 || target < 0) return ;
// Max times for the current number.
int curIndex = length - 1;
int maxTimes = target / candidates[curIndex];
for (int i = maxTimes; i >= 0; i--) {
times[curIndex] = i;
combinationSum(res, candidates, curIndex, times, target - i * candidates[curIndex]);
}
}``````

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