A simple solution using backtracing


  • 0
    C
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            helper(candidates, target, 0, 0, result, new ArrayList<Integer>());
            
            return result;
        }
        
        private void helper(int[] candidates, int target, int index, int sum, List<List<Integer>> result, List<Integer> sol) {
            if (sum == target) {
                result.add(new ArrayList<Integer>(sol));
                return;
            } else if (sum < target) {
                for(int i = index; i < candidates.length; i++) {
                    sol.add(candidates[i]);
                    
                    helper(candidates, target, i, sum+candidates[i], result, sol);
                    
                    sol.remove(sol.size() - 1);
                }
            } else {
                return;
            }
        }
    }

Log in to reply
 

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