package com.freetymekiyan.algorithms.level.medium;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * Given a set of distinct integers, nums, return all possible subsets.
 * <p>
 * Note: The solution set must not contain duplicate subsets.
 * <p>
 * For example,
 * If nums = [1,2,3], a solution is:
 * <p>
 * | [
 * |   [3],
 * |   [1],
 * |   [2],
 * |   [1,2,3],
 * |   [1,3],
 * |   [2,3],
 * |   [1,2],
 * |   []
 * | ]
 * Company Tags: Amazon, Uber, Facebook
 * Tags: Array, Backtracking, Bit Manipulation
 * Similar Problems: (M) Generalized Abbreviation
 */
public class Subsets {

    private Subsets s;

    /**
     * Backtracking.
     * Visit:
     * Backtrack without current number.
     * Then add the number and backtrack again.
     * Reset.
     * Base case:
     * When the end of array is reached, add de-referenced subset to result and return.
     */
    public List<List<Integer>> subsetsA(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrackA(res, nums, 0, new ArrayList<>());
        return res;
    }

    private void backtrackA(List<List<Integer>> res, int[] nums, int pos, List<Integer> subset) {
        if (pos == nums.length) {
            res.add(new ArrayList<>(subset));
            return;
        }
        backtrackA(res, nums, pos + 1, subset); // Without current number.
        subset.add(nums[pos]);
        backtrackA(res, nums, pos + 1, subset); // With current number.
        subset.remove(subset.size() - 1); // Reset.
    }

    /**
     * Backtracking.
     */
    public List<List<Integer>> subsetsB(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        subsetsB(res, nums, 0, new ArrayList<>());
        return res;
    }

    /**
     * DFS.
     * Add current subset to result first.
     * Put current number in subset.
     * Then backtrack with the rest of the numbers.
     * Reset by remove last number in subset.
     * Next iteration will move to next number then all subsets will not have this number.
     */
    public void subsetsB(List<List<Integer>> sets, int[] nums, int pos, List<Integer> subset) {
        sets.add(new ArrayList<>(subset)); // Dereference and add current subset to result.
        for (int i = pos; i < nums.length; i++) {
            subset.add(nums[i]); // With nums[i].
            subsetsB(sets, nums, i + 1, subset); // Backtrack to generate add subsets with s[i].
            subset.remove(subset.size() - 1); // Remove s[i], next round there won't be s[i].
        }
    }

    /**
     * Iterative.
     * Build from empty set to the next subsets.
     * Adding each subset the current num, new subsets are generated.
     * Then add new subsets to all subsets and generate next round.
     * Stop when we iterate through the array.
     * E.g.:
     * [] -> [] [1]
     * [] [1] -> [] [1] [2] [1, 2]
     */
    public List<List<Integer>> subsetsC(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<>()); // Add empty set.
        for (int i = 0; i < nums.length; i++) {
            int n = subsets.size();
            for (int j = 0; j < n; j++) {
                List<Integer> set = new ArrayList<>(subsets.get(j)); // Dereference.
                set.add(nums[i]);
                subsets.add(set);
            }
        }
        return subsets;
    }


    @Before
    public void setUp() {
        s = new Subsets();
    }

    @Test
    public void testExamples() {
        int[] nums = {1, 2, 3};
        List<List<Integer>> res = s.subsetsB(nums);
        System.out.println(res.toString());
    }

    @After
    public void tearDown() {
        s = null;
    }
}

@@ -49,81 +49,8 @@
 m;%0A%0A
-import org.junit.After;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A
 impo
@@ -101,16 +101,38 @@
 t;%0A%0A/**%0A
+ * 78. Subsets%0A * %3Cp%3E%0A
  * Given
@@ -618,32 +618,8 @@
  %7B%0A%0A
-    private Subsets s;%0A%0A
     
@@ -912,17 +912,16 @@
  subsets
-A
 (int%5B%5D n
@@ -989,33 +989,32 @@
        backtrack
-A
 (res, nums, 0, n
@@ -1085,17 +1085,16 @@
 acktrack
-A
 (List%3CLi
@@ -1275,33 +1275,32 @@
        backtrack
-A
 (res, nums, pos 
@@ -1388,17 +1388,16 @@
 acktrack
-A
 (res, nu
@@ -1576,17 +1576,17 @@
  subsets
-B
+2
 (int%5B%5D n
@@ -1660,17 +1660,17 @@
  subsets
-B
+2
 (res, nu
@@ -2043,17 +2043,17 @@
  subsets
-B
+2
 (List%3CLi
@@ -2065,16 +2065,19 @@
 teger%3E%3E 
+sub
 sets, in
@@ -2101,35 +2101,32 @@
 , List%3CInteger%3E 
-sub
 set) %7B%0A        s
@@ -2124,16 +2124,19 @@
         
+sub
 sets.add
@@ -2148,27 +2148,24 @@
 ArrayList%3C%3E(
-sub
 set)); // De
@@ -2262,35 +2262,32 @@
 ) %7B%0A            
-sub
 set.add(nums%5Bi%5D)
@@ -2291,25 +2291,8 @@
 i%5D);
- // With nums%5Bi%5D.
 %0A   
@@ -2307,18 +2307,21 @@
  subsets
-B(
+2(sub
 sets, nu
@@ -2327,27 +2327,24 @@
 ums, i + 1, 
-sub
 set); // Bac
@@ -2389,35 +2389,32 @@
 i%5D.%0A            
-sub
 set.remove(subse
@@ -2400,35 +2400,32 @@
      set.remove(
-sub
 set.size() - 1);
@@ -2864,17 +2864,17 @@
  subsets
-C
+3
 (int%5B%5D n
@@ -3332,322 +3332,5 @@
   %7D%0A
-%0A%0A    @Before%0A    public void setUp() %7B%0A        s = new Subsets();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        int%5B%5D nums = %7B1, 2, 3%7D;%0A        List%3CList%3CInteger%3E%3E res = s.subsetsB(nums);%0A        System.out.println(res.toString());%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        s = null;%0A    %7D%0A%7D%0A
+%7D

update 78. Subsets