My Java solution(recursive)


  • 0
    A
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> results = new ArrayList<>();
            if (candidates == null) {
                return results;
            }
            Arrays.sort(candidates);
            helper(candidates, target, new ArrayList<Integer>(), results, 0, 0);
            return results;
        }
        private void helper(int[] candidates, int target, List<Integer> list, List<List<Integer>> results, int sum, int index) {
            if (sum == target) {
                results.add(new ArrayList<>(list));
                return;
            }
            int n = candidates.length;
            for (int i = index; i < n; i++) {
                if (sum + candidates[i] <= target) {
                    list.add(candidates[i]);
                    helper(candidates, target, list, results, sum + candidates[i], i);
                    list.remove(list.size() - 1);
                } else {
                    break;
                }
            }
        }
    }

Log in to reply
 

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