[combination] [Backtracking][Bit manipulation] Subsets

1. Example
Sub +Set = distinguish set
nums = [1,2,3], a solution is:

[
[],

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

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

[1,2,3]

]

2. Implementation
Q1: combination?
A1: 2^n, n is the length of array
Q1: how to start? recursive ? avoid repeated element ?
A1: (nums, index+1), base case
Step1:

item = [], res=[    []    ], recursive call h: index from 0
for loop add single element i = 0,1,2
           i=0, item=   []+[1] , res [  [], [1]  ], recursive call h:  [1], index from 1
           for loop add single element 1,2
                   i=1, item = [1]+[2] , res =[ [], [1], [1,2] ], recursive call h:  [1], index from 2
                   for loop, i = 2
                          i =2, item = [1,2] +[3], res =[ [], [1], [1,2] , [1,2,3]  ]
                          out of loop return !!!!!!!!!!!
                   i=2, item = [1]+[3]
           i=1, item =  []+[2], recursive call h: [2] , index from 2
           for loop add single element 1,2
                  i=2, item =  [2] + [3]   
           i=2, item =  []+[3]
Distinguish/Separate element additon, every time add specific and different element by using existing solution
// NOTE: Recursive

if (index == -1 ) { 

 List<Integer> res = new ArrayList(); 

 List item = new ArrayList();

 res.add(item); 

 return res;

 }

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

int size_unchanged_with_res = res.size();

 for(int i = 0; i < size_unchanged_with_res ; i++) { 

 List item = new ArrayList(res.get(i)); 

// NOTE: we add one item into multiple existing solution 

 item.add( num[index] ); 

 res.add( item ); 

 }

// NOTE: Iterative

for (int i = 0; i < nums.length; i++) {

int size = res.size(); 

 for ( int j = 0 ; j < size; j++) { 

 List item = new Arraylist(res.get(i)); 

 item.add(nums[i]); 

 res.add(item); 

 }

// NOTE: we add one item into multiple existing solution
           item.add(   num[index]  );
// NOTE:
Arrays.sort(nums);

// Recursive, bottom-up approach, h(h(h(h(-1))))
// Time:O(2^n), Space:O(2^n) list>

public List> subsets (int[] nums)
{

      List> res = new ArrayList>();
      


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



      //List item = new ArrayList();
      //res.add(item); // like pascal's triangle, for loop numberofRows and core prev[i] = prev[i] + prev[i-1], i-1 >=0 
      // NOTE: merge into recursive call

      
      Arrays.sort(nums);




      //helper(nums, 0,item,res);
      // NOTE: adopt bottom-up approach
      res = helper( nums, nums.length-1 );


      return res;



}
//private void helper(int[] nums, int start, List item, List> res)
private List>  helper(int[] nums, int index)
{
   



      //for (int i = start; i < nums.length; i ++)
      //{
      //        List newItem = new ArrayList (   item.add(nums[i]) );
      //        res.add(newItem);
      //        helper(nums, i+1, newItem ,res);
      //}
      //return;


      // Base case
      // NOTE: bring first case in main function into helper as base case
      if (index == -1 )
      {
           List> res = new ArrayList();
           res.add(new ArrayList());
           return res;
      }



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


  
      int size_unchanged_with_res = res.size();
      for(int i = 0; i < size_unchanged_with_res ; i++)
      {
            List item = new ArrayList(res.get(i));
            // NOTE: we add one item into multiple existing solution
            item.add(   num[index]  );
            res.add( item );
      }


     
      return res;



}

// Iterative approach: top down , from [] to [1,2,3]
public List> subsets(int[] nums)
{


        List> res = new ArrayList>();

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


         
       res.add( new ArrayList());
       Arrays.sort(nums);

      
       for (int i = 0; i < nums.length; i++)
       {
             int size = res.size();
             for ( int j = 0 ; j < size; j++)
             {
                    List item = new Arraylist(res.get(i));
                    item.add(nums[i]);
                    res.add(item);
             }
       }

     

       return res;

}
suppose [1,2,3]
[]
i = 0, add[1]
j = 0
[]+[1] =[1]
[],[1]
i = 1, add[2]
j = 0
[]+[2] = [2]
j = 1
[1]+[2] =[1,2]
[],[1],[2],[1,2]
i = 2,  add[3]
j=0
j=1
j=2  

3. Similar Ones
combination =>  sort

subsets II