package com.freetymekiyan.algorithms.level.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Given a collection of integers that might contain duplicates, nums, return all possible subsets.
 * <p>
 * Note: The solution set must not contain duplicate subsets.
 * <p>
 * For example,
 * If nums = [1,2,2], a solution is:
 * <p>
 * | [
 * |   [2],
 * |   [1],
 * |   [1,2,2],
 * |   [2,2],
 * |   [1,2],
 * |   []
 * | ]
 * Company Tags: Facebook
 * Tags: Array, Backtracking
 */
public class Subsets2 {

    /**
     * Backtracking.
     * Sort the array first for skipping duplicates later.
     */
    public List<List<Integer>> subsetsWithDup(int[] num) {
        if (null == num || num.length == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(num); // Sort first.
        backtrack(res, num, 0, new ArrayList<>());
        return res;
    }

    /**
     * Backtracking. DFS.
     * Traverse a each node of a solution tree.
     * For each number n in the nums array:
     * | If n is a duplicate of previous number, skip.
     * | Pick it and backtrack.
     * | Remove it.
     */
    private void backtrack(List<List<Integer>> res, int[] nums, int pos, List<Integer> subsets) {
        res.add(new ArrayList<>(subsets)); // Dereference.
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) { // Check and skip duplicates.
                continue;
            }
            subsets.add(nums[i]); // Add.
            backtrack(res, nums, i + 1, subsets); // Backtrack.
            subsets.remove(subsets.size() - 1); // Reset.
        }
    }

    /**
     * Backtracking.
     * Duplicate with previous number will only be added if:
     * The previous number is already in subset.
     */
    private void backtrackB(List<List<Integer>> res, int[] nums, int pos, List<Integer> subset) {
        if (pos == nums.length) {
            res.add(new ArrayList<>(subset)); // Dereference.
            return;
        }
        subset.add(nums[pos]); // Add.
        backtrack(res, nums, pos + 1, subset); // Backtrack.
        subset.remove(subset.size() - 1); // Reset.
        if (pos > 0 && nums[pos] == nums[pos - 1] && !subset.isEmpty() && nums[pos - 1] == subset
            .get(subset.size() - 1)) {
            return;
        }
        backtrack(res, nums, pos + 1, subset);
    }

    /**
     * DP. Bottom-up.
     * Build subsets level by level from empty set.
     * For each number n in nums:
     * | If n is not a duplicate:
     * |   Insert n to each previous subsets and create new subsets.
     * | If n is a duplicate:
     * |   Only need to insert n to the subsets that contains a previous duplicate.
     * E.g. [1 2 2]
     * [] => [], [1] => [], [1], [2], [1 2] => [], [1], [2], [1 2], [2 2], [1 2 2]
     * Add 2 to subsets which have 2, which is the latter half of result.
     */
    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>()); // Empty set.
        if (null == nums || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums); // Sort first.

        int j, prevSize = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) { // Duplicate.
                j = prevSize; // # of previous sets before last number.
            } else {
                j = 0; // No dup, start from beginning.
            }
            prevSize = res.size(); // # of previous sets.
            // Add to previous sets with same num
            for (; j < prevSize; j++) {
                List<Integer> temp = new ArrayList<>(res.get(j));
                temp.add(nums[i]);
                res.add(temp);
            }
        }
        return res;
    }
}
@@ -156,16 +156,41 @@
 t;%0A%0A/**%0A
+ * 90. Subsets II%0A * %3Cp%3E%0A
  * Given
@@ -868,34 +868,38 @@
 %3CList%3CInteger%3E%3E 
-re
+subset
 s = new ArrayLis
@@ -960,26 +960,30 @@
   backtrack(
-re
+subset
 s, num, 0, n
@@ -1008,34 +1008,38 @@
 %0A        return 
-re
+subset
 s;%0A    %7D%0A%0A    /*
@@ -1100,23 +1100,21 @@
 e of a s
-olution
+ubset
  tree.%0A 
@@ -1310,34 +1310,38 @@
 %3CList%3CInteger%3E%3E 
-re
+subset
 s, int%5B%5D nums, i
@@ -1362,23 +1362,19 @@
 nteger%3E 
-sub
 set
-s
 ) %7B%0A    
@@ -1369,34 +1369,38 @@
  set) %7B%0A        
-re
+subset
 s.add(new ArrayL
@@ -1405,23 +1405,19 @@
 yList%3C%3E(
-sub
 set
-s
 )); // D
@@ -1610,31 +1610,27 @@
             
-sub
 set
-s
 .add(nums%5Bi%5D
@@ -1631,24 +1631,16 @@
 ums%5Bi%5D);
- // Add.
 %0A       
@@ -1646,34 +1646,38 @@
       backtrack(
-re
+subset
 s, nums, i + 1, 
@@ -1676,23 +1676,19 @@
  i + 1, 
-sub
 set
-s
 ); // Ba
@@ -1686,32 +1686,71 @@
 t); // Backtrack
+ the rest of the numbers, so i -%3E i + 1
 .%0A            su
@@ -1751,23 +1751,19 @@
     
-sub
 set
-s
 .remove(
 subs
@@ -1758,23 +1758,19 @@
 .remove(
-sub
 set
-s
 .size() 
@@ -1770,34 +1770,24 @@
 size() - 1);
- // Reset.
 %0A        %7D%0A 
@@ -1965,17 +1965,17 @@
 acktrack
-B
+2
 (List%3CLi
@@ -2211,32 +2211,33 @@
        backtrack
+2
 (res, nums, pos 
@@ -2426,16 +2426,20 @@
         
+    
 .get(sub
@@ -2504,16 +2504,17 @@
 acktrack
+2
 (res, nu

update 90. Subsets II