Java dp simple solution


  • 0
    V
    public class Solution {
        HashMap<Integer, Set<List<Integer>>> dp = new HashMap<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            return new ArrayList<>(getLists(candidates, target));
        }
        
        private Set<List<Integer>> getLists(int[] candidates, int target){
            if(target <= 0) return null;
            if(dp.containsKey(target)) return dp.get(target);
            Set<List<Integer>> list = new HashSet<List<Integer>>();
            for(int i : candidates){
                if(target < i) break;
                if(target == i){
                    List<Integer> ll = new ArrayList<Integer>();
                    ll.add(i);
                    Collections.sort(ll);
                    list.add(ll);
                } else{
                    Set<List<Integer>> l = dp.containsKey(target-i) ? dp.get(target-i):getLists(candidates, target - i);
                    if(l != null){
                        for(List<Integer> lll : l){
                            List<Integer> llll = new ArrayList<Integer>(lll);
                            llll.add(i);
                            Collections.sort(llll);
                            list.add(llll);
                        }
                    }
                }
            }
            dp.put(target, list);
            return list;
        }
    }

Log in to reply
 

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