Any better solution? for combination sum II


  • 0
    O

    I get a accepted answer with 640 ms, looking for a better solution. And I'm also not quite sure about the time complexity, please share some minds, thanks!

        public class Solution 
        {
        	private Map<Integer, Set<List<Integer>>> map = new HashMap<Integer, Set<List<Integer>>>();
            public List<List<Integer>> combinationSum2(int[] num, int target) 
            {
            	Set<List<Integer>> tl = new HashSet<List<Integer>>();
            	tl.add(new ArrayList<Integer>());
                map.put(0, tl);
            	Arrays.sort(num);
            	for(int i : num)
            	{
            		if(i>target)
            			break;
            		List<Integer> tmp = new ArrayList<Integer>(map.keySet());
            		Collections.sort(tmp, Collections.reverseOrder());
            		for(int k : tmp)
            		{
            			if(k+i<=target)
            			{
            				Set<List<Integer>> list = map.get(k);
            				Set<List<Integer>> newList;
            				if(map.containsKey(k+i))
            					newList = map.get(k+i);
            				else
            					newList = new HashSet<List<Integer>>();
            				
            				for(List<Integer> subList : list)
            				{
            					List<Integer> nl = new ArrayList<Integer>(subList);
            					nl.add(i);
            					newList.add(nl);
            				}
            				map.put(k+i,newList);
            			}
            		}
            	}
        		if(map.containsKey(target))
        		    return new ArrayList<List<Integer>>(map.get(target));
        		else
        		    return new ArrayList<List<Integer>>();
        }
    }

Log in to reply
 

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