[Combination][Backtracking] Subsets II

1. Example
Contain Duplicate

s=[1,2,2], a solution set is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


2. Implementation
Q1: distinguish addition?
A1: num[index] or num[i] will have duplicate, so adding to existing solution would result duplicate subsets. Avoid?
make sure  num[index] or num[i] are not the same as their previous one and do the addition
Q1: BUT you also avoid the cases like [c,c] or [a,c,c] except avoiding cases such as [a,c](from[a]), [c](from[]). How to fix?
A1: item[], item[a] should be avoided. How do you record that, record the start of adding position
Suppose [1,1,2]
When [] you got addFromIndex = res.size()=0 res=[ ]
when [1] you got addFromIndex = res.size() = 1, res=[ [] ]
when [2] you got addFromIndex  = res.size()=2, res=[ [],[1] ]
when [2] you got addFromIndex = res.size() =4 ,res = [ [], [1], [2], [1,2]] . We use second 2's addFromIndex 2 as a base existing solution and add on [2],[1,2] =>[2,2], [1,2,2]




Input:[1,1]
Output:[[],[1],[1],[1,1]]
Expected:[[],[1],[1,1]]

// Recursive
// adding into existing, base case []
// Time:O(2^n), Space:O(2^n)
public List> subsetsWithDup(int[] nums)
{


       
       List> res = new ArrayList>(); 

      

       // validate the input
       if ( nums == null || nums.length == 0)
       {
            return res;
       }



       Arrays.sort(nums);



       // NOTE: record start adding position for each num[index]
       List lastSize = new ArrayList();
       lastSize.add(0); 
       return helper(nums, nums.length - 1, lastSize);



}
private List> helper(int[] nums, int index, List lastSize)
{




       
       // Base case 
       if (index = -1 )
       {
             List item = new ArrayList();
             List> res = new ArrayList>();
             res.add(item);
             //positionSet.add(res.size());
             return res;
       }





       List<List<Integer>> res = helper(nums, index -1);


       

 
       // NOTE: SubsetsII newly added compare to subset I to avoid duplicate set
       int start = 0;
       // NTOE: inside helper, out index start from -1,0,1...to len-1
       //if ( index != nums.length -1 && nums[index] == nums[index+1] )
            //start = positionSet.get(index+1);
        if (  index > 0 && nums[index] == nums[index-1] )            start = lastSize.get(0);






       int size_unchanged = res.size();
       // NOTE: SubsetsII
       for (int j = start ; j < size_unchanged; j++)
       { 






           // NOTE:
           //if ( index != nums.length -1 && nums[index] != nums[index+1]  )
           //{
                 List<Integer> item = new ArrayList<Integer>(  res.get(j) );
                 item.add( nums[index] );
                 res.add(item);
           //}
       


       }




       //lastSize.add(res.size());
       lastSzie.set(0, size_unchanged);
       return res;




}

// Iterative
// nested loop and adding into existing, add [] in the very first
// Time:O(2^n), Space:O(2^n)
public List<List<Integer>> subsetsWithDup(int[] nums)
{


   List<List<Integer>> res = new ArrayList<List<Integer>>();
   


   // validate the input      
   if ( nums == null || nums.length == 0)
          return res;    



   Arrays.sort(nums);      




   List<Integer> lastSize = new ArrayList<Integer>();
   lastSize.add(0);
   int size_unchanged = 0;    
   for (int i = 0 ; i < nums.length ;i++)   
   {        




          // NOTE: subsets II
          int start = 0;
          if ( i >0 && nums[i] == nums[i-1] )
                 start = lastSize.get(0);


        

           int size_unchanged = res.size();
           for (int j = start; j < size_unchanged; j++)
           //for (int j = 0; j< size_unchanged; j++)          
           {                 
               List<Integer> item = new ArrayList<Integer>(res.get(j));
               item.add(nums[i]); 
               res.add(item);

           }


           lastSize.set(0,size_unchanged);

    }


     return res;

}

3. Similar Ones
Subsets I
Combination Sum I/II (random combination sum equal to target value)