My simple Java solution (backtracking)


  • 1
    R
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List result = new ArrayList();
            if (candidates == null || candidates.length == 0) {
                return result;
            }
            Arrays.sort(candidates);
            Set solutions = new HashSet();
            helper(candidates, target, result, new ArrayList<Integer>(), 0, solutions);
            return result;
        }
        
        private void helper(int[] candidates, int target, List result, List<Integer> solution, int pos, Set solutions) {
            int sum = 0;
            for (int i = 0; i < solution.size(); i++) {
                sum += solution.get(i);
            }
            if (sum > target) {
                return;
            }
            
            if (sum == target) {
                if (!solutions.contains(solution)) {
                    result.add(new ArrayList<Integer>(solution));
                    solutions.add(solution);
                    return;
                }
            }
            
            for (int i = pos; i < candidates.length; i++) {
                solution.add(candidates[i]);
                helper(candidates, target, result, solution, i+1, solutions);
                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.