Java solution ( hope sb can optimize)


  • 0
    X
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> rst = new ArrayList<List<Integer>>();
            List<List<Integer>> rst2 = new ArrayList<List<Integer>>();
            List<Integer> list = new ArrayList<Integer>();
            Arrays.sort(candidates);
            int sum = 0;
            helper(candidates, target, sum, rst, list, 0);
            // Map<List<Integer>, Integer> map= new Map<List<Integer>, Integer>();
            HashSet set = new HashSet();
            for(int i = 0; i < rst.size(); i++){
                if(!set.contains(rst.get(i))){
                    set.add(rst.get(i));
                    rst2.add(rst.get(i));
                }
            }
            
            return rst2;
            
        }
        
        public void helper(int[] nums, int target, int sum, List<List<Integer>> rst, List<Integer> list, int start){
            if(sum == target){
                rst.add(new ArrayList(list));
                return;
            }
            for(int i = start; i < nums.length; i++){
                if(sum + nums[i] <= target){
                    list.add(nums[i]);
                    helper(nums, target, sum + nums[i], rst, list, i + 1);
                    list.remove(list.size() - 1);
                }else{
                    return;
                }
            }
        }
    }

  • 0
    S

    I always worry the HashSet is dangerous or time-consuming.


Log in to reply
 

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