A recursive solution by JAVA


  • 0

    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)
                    list.add(candidates[i]);
            }
            res.add(list);
            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]);
        }
    }

Log in to reply
 

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