Share my 2ms java iteration solution (very simple and short)


  • 25
    S
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	result.add(new ArrayList<Integer>());
    	int begin = 0;
    	for(int i = 0; i < nums.length; i++){
    		if(i == 0 || nums[i] != nums[i - 1]) begin = 0;
    		int size = result.size();
    		for(int j = begin; j < size; j++){
    			List<Integer> cur = new ArrayList<Integer>(result.get(j));
    			cur.add(nums[i]);
    			result.add(cur);
    		}
    		begin = size;
    	}
    	return result;
    }

  • 0
    O

    Great coding


  • 0
    A
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
            List<IList<int>> res = new List<IList<int>>();
            res.Add(new List<int>());  // []
            Array.Sort(nums);
            int dupStart = 1;
            for (int i=0; i<nums.Length; i++){
                int count = res.Count, start=0;
                if (i>0 && nums[i]==nums[i-1]){  // duplicate
                    start = dupStart;
                }
                for (int j=start; j<count; j++){
                    List<int> seq = new List<int>(res[j]);
                    seq.Add(nums[i]);
                    res.Add(seq);
                }
                dupStart = count;
            }
            return res;
        }
    

    Similar idea here. Not sure why there's a tag of backtracking, it looks more like DP.


  • 0
    S

    If the outer loop starts from i = 0 then nums[i - 1] will cause IndexOutOfBound, and we don't need to check for i == 0 to set begin = 0, since begin is already 0 when the loop first starts.


  • 1
    Y

    i == 0 is needed,for "||",if the first condition is ok,it doesn't check the second condition.without i==0, exception will happen


  • 0
    B

    Agree. Should be tagged DP instead of backtracking.


  • 0
    P

    No more a 2 ms solution. It takes 3 ms now :)


Log in to reply
 

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