Subsets, Subsets II, Missing Ranges

Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

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

Non-recursive Solution

Just keep adding current number to the result collection..
Pay attention to the use of add and addAll

i=0 | [[], [1]]
i=1 | [[2], [1,2]]
i=2 | [[3], [1,3], [2,3], [1,2,3]]

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        //add empty set
        subsets.add(new ArrayList<Integer>());
        //add set from layers 
        for(int i=0;i<S.length;i++){
             ArrayList<ArrayList<Integer>> subsetsfori=new ArrayList<ArrayList<Integer>>();
            for(ArrayList<Integer> prev: subsets){
                ArrayList<Integer> tmp= new ArrayList<Integer>();
                tmp.addAll(prev);
                tmp.add(S[i]);
                subsetsfori.add(tmp);
        }
        subsets.addAll(subsetsfori);
    }
    return subsets;
}

Recursive Solution

Similar to DFS, i refers to start position of a subset

i=0 | [[], [1], [1,2], [1,2,3]]
i=1 | [[2], [2,3]]
i=2 | [[3]]

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        subsets.add(new ArrayList<Integer>());
        subset_helper(subsets, subset, 0, S);
    return subsets;
}
    private  void subset_helper(ArrayList<ArrayList<Integer>> subsets, ArrayList<Integer> subset, int start, int[] s){
        for(int i=start;i<s.length;i++){
            subset.add(s[i]);
            //add new arraylist subset here
            subsets.add(new ArrayList<Integer>(subset));
            subset_helper(subsets, subset, i+1, s);
            subset.remove(subset.size()-1);
        }
    }

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:

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

Only difference is the added while loop.
If completed current layer, and found the next element is the same then skip.

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
          Arrays.sort(num);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        subsets.add(new ArrayList<Integer>());
        subset_helper(subsets, subset, 0, num);
    return subsets;
    }
    
  private  void subset_helper(ArrayList<ArrayList<Integer>> subsets, ArrayList<Integer> subset, int start, int[] s){
  for(int i=start;i<s.length;i++){
      subset.add(s[i]);
      //add new arraylist subset here
      subsets.add(new ArrayList<Integer>(subset));
      subset_helper(subsets, subset, i+1, s);
      subset.remove(subset.size()-1);
      while(i < s.length-1 && s[i]==s[i+1]) 
      {i++;}
  }
}

Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

Main idea: output accrodingly when two elements differ>=2, pay attention to edge cases.

public ArrayList<String> findmissingRanges(int[] num, int lower, int upper){
    ArrayList<String> res=new ArrayList<String>();
   
      if(num.length==0){
        if(lower!=upper) res.add(lower+"->"+upper);
        else res.add(lower+"");
        return res;
      }
      if(lower<num[0]){
        if(num[0]-lower>1) res.add(lower+"->"+(num[0]-1));
        else res.add(lower+"");
      }
      
      for(int i = 0;i<num.length-1;i++){
        if(num[i+1]-num[i]>2) res.add((num[i]+1)+"->"+(num[i+1]-1)+"");
        else if(num[i+1]-num[i]==2) res.add(num[i]+1+"");
        else continue;
      }
      
      if(num[num.length-1]<upper){
        if(upper-num[num.length-1]>1) res.add(num[num.length-1]+1+"->"+upper);
        else res.add(""+upper);
      }
      return res;
  }

More Concise:

public List<String> findMissingRanges(int[] vals, int start, int end) {
       List<String> ranges = new ArrayList<String>();
       int prev = start - 1;
       for (int i=0; i<=vals.length; i++) {
           int curr = (i==vals.length) ? end + 1 : vals[i];
           if ( curr-prev>=2 ) {
               ranges.add(getRange(prev+1, curr-1));
           }
           prev = curr;
       }
       return ranges;
   }
   private String getRange(int from, int to) {
       return (from==to) ? String.valueOf(from) : from + "->" +to;
   }