My simple Java Solution (Backtracking)


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

Log in to reply
 

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