Subsets II

class Solution {
public:
    vector<vector<int>> uniqueSubsets(vector<int>& input) {
        vector<vector<int>> result;
        vector<int> tempSubset;
        sort(input.begin(), input.end());
        generateSubsets(result, tempSubset, input, 0);
        return result;
    }
    
private:
    void generateSubsets(vector<vector<int>>& result,
                         vector<int>& tempSubset, vector<int>& input,
                         int startIndex) {
        result.push_back(tempSubset);
    
        for (int i = startIndex; i < input.size(); i++) {
            if (i != startIndex && input[i] == input[i - 1]) {
                continue;
            }
            tempSubset.push_back(input[i]);
            generateSubsets(result, tempSubset, input, i + 1);
            tempSubset.pop_back();
        }
    }
};

The provided C++ solution addresses the problem of generating all unique subsets from a given list of integers that may contain duplicates. Here's a breakdown of the code:

• The uniqueSubsets function begins by sorting the input list to facilitate the handling of duplicates. This is a common approach in subset problems involving duplicates, as it allows for easier comparison between consecutive elements.
• A result vector of vectors is declared to store each subset, and a tempSubset vector is used to hold the current subset being constructed.
• The generateSubsets private helper function is recursively called to build all possible subsets. It starts by adding the tempSubset (representing a subset) to result.
• Within generateSubsets, a loop iterates through the elements of the input vector starting from startIndex. The conditional statement if (i != startIndex && input[i] == input[i - 1]) ensures that duplicates do not lead to duplicate subsets by skipping over duplicates that are not at the start index of the current recursive function call.
• For each element not skipped, the function adds the element to tempSubset and recursively calls itself with the incremented start index (i + 1). This allows the function to explore subsets that include the current element.
• After the recursive call, the function backtracks by removing the last element added to tempSubset (i.e., tempSubset.pop_back()), effectively exploring subsets that do not include the current element.

This solution effectively generates all unique subsets by handling duplicates through sorting and conditional continuation within the loop, thereby ensuring each unique subset is recorded only once. The use of recursion with backtracking is a typical method in solving subset problems, allowing the exploration of all potential combinations efficiently.

class Solution {
    public List<List<Integer>> generateSubsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> resultSubsets = new ArrayList<>();
        List<Integer> tempSubset = new ArrayList<>();
    
        backtrack(resultSubsets, tempSubset, nums, 0);
        return resultSubsets;
    }
    
    private void backtrack(
        List<List<Integer>> resultSubsets,
        List<Integer> tempSubset,
        int[] nums,
        int startIndex
    ) {
        resultSubsets.add(new ArrayList<>(tempSubset));
    
        for (int j = startIndex; j < nums.length; j++) {
            if (j != startIndex && nums[j] == nums[j - 1]) {
                continue;
            }
            tempSubset.add(nums[j]);
            backtrack(resultSubsets, tempSubset, nums, j + 1);
            tempSubset.remove(tempSubset.size() - 1);
        }
    }
}

The given Java solution tackles the problem of generating all possible subsets of a given integer array while ensuring each subset is unique, even if the original array contains duplicates. This problem is effectively addressed using a backtracking approach. Here's how the solution works:

• The input array nums is first sorted. Sorting is crucial as it helps in easily skipping duplicates and ensuring the sets are unique.
• An ArrayList resultSubsets is initialized to store the subsets.
• Another ArrayList tempSubset is used to maintain the current subset being explored.
• The backtrack method is recursively called starting from the first index of the array. This method is the heart of the solution, where subsets are built and explored.
• Within backtrack, the current subset (tempSubset) is added to resultSubsets.
• The method then iterates over the array elements starting from startIndex. If the current element is the same as the one before it and is not at the start of the loop, it skips the element to avoid duplicates.
• If the element is not a duplicate, it is added to tempSubset, and backtrack is called recursively with the next index.
• After the recursive call, the last element is removed from tempSubset to backtrack and explore other potential elements to include in the subset.

This approach ensures that all unique subsets are considered without redundantly processing duplicates, leveraging both the sorted nature of the array and the mechanism of recursion combined with backtracking.

typedef struct {
    int* elements;
    int size;
} ArrayList;
    
void list_initialize(ArrayList* list) {
    list->elements = NULL;
    list->size = 0;
}
    
void list_add(ArrayList* list, int element) {
    list->elements = realloc(list->elements, sizeof(int) * (list->size + 1));
    list->elements[list->size] = element;
    list->size++;
}
    
void list_remove(ArrayList* list) {
    list->size--;
    list->elements = realloc(list->elements, sizeof(int) * list->size);
}
    
typedef struct {
    ArrayList* lists;
    int size;
} ArrayListSet;
    
void list_set_initialize(ArrayListSet* set) {
    set->lists = NULL;
    set->size = 0;
}
    
void list_set_add(ArrayListSet* set, ArrayList* list) {
    set->lists = realloc(set->lists, sizeof(ArrayList) * (set->size + 1));
    set->lists[set->size] = *list;
    set->lists[set->size].elements = (list->size > 0) ? malloc(list->size * sizeof(int)) : NULL;
    if (list->size > 0) {
        memcpy(set->lists[set->size].elements, list->elements, list->size * sizeof(int));
    }
    set->size++;
}
    
int compare_elements(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
    
void generateSubsets(ArrayListSet* allSubsets, ArrayList* currentSubset, int* nums, int numsSize, int index) {
    list_set_add(allSubsets, currentSubset);
    for (int i = index; i < numsSize; i++) {
        if (i != index && nums[i] == nums[i - 1]) continue;
        list_add(currentSubset, nums[i]);
        generateSubsets(allSubsets, currentSubset, nums, numsSize, i + 1);
        list_remove(currentSubset);
    }
}
    
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare_elements);
    ArrayListSet allSubsets;
    list_set_initialize(&allSubsets);
    ArrayList currentSubset;
    list_initialize(&currentSubset);
    generateSubsets(&allSubsets, &currentSubset, nums, numsSize, 0);
    free(currentSubset.elements);
    *returnSize = allSubsets.size;
    *returnColumnSizes = (int*)malloc(sizeof(int) * allSubsets.size);
    int** result = (int**)malloc(sizeof(int*) * allSubsets.size);
    for (int i = 0; i < allSubsets.size; i++) {
        (*returnColumnSizes)[i] = allSubsets.lists[i].size;
        result[i] = (allSubsets.lists[i].size > 0) ? (int*)malloc(sizeof(int) * allSubsets.lists[i].size) : NULL;
        for (int j = 0; j < allSubsets.lists[i].size; j++) {
            result[i][j] = allSubsets.lists[i].elements[j];
        }
        free(allSubsets.lists[i].elements);
    }
    free(allSubsets.lists);
    return result;
}

This solution in C implements a function for generating all possible subsets of a given integer array, ensuring that duplicates in the input do not produce duplicate subsets in the output. Here's an explanation of the primary components and their roles:

• Structures and Initialization

  • ArrayList and ArrayListSet structures are defined to manage dynamic arrays and sets of arrays respectively.
  • list_initialize and list_set_initialize functions prepare these structures for use by setting initial values and allocating necessary memory.

• Adding and Removing Elements

  • list_add and list_remove are functions to dynamically adjust the size of an ArrayList as elements are added or removed during the subset generation process.
  • list_set_add is used to add a complete ArrayList to an ArrayListSet. This function handles deep copying of elements to ensure that each subset is saved independently.

• Subset Generation

  • The generateSubsets function recursively generates subsets. It starts with an empty subset and explores all possible combinations by including each number from the input set sequentially.
  • To avoid duplicate subsets due to identical elements in the input, the function skips over duplicates by checking if the current number is the same as the previous one, unless it's the start of a new subset chain.

• Sorting and Returning Results

  • The main function subsetsWithDup begins by sorting the input array to simplify duplicate detection.
  • After generating all subsets using generateSubsets, the subsets are transformed into a standard format for the result; this includes allocating memory for each subset and copying the subset data into a return array format suitable for output.
  • Memory management is carefully handled, with all allocated memory being freed appropriately to prevent memory leaks.

This approach ensures that the solution not only provides the correct subsets, including handling arrays with duplicates, but also manages memory efficiently in a language like C, where manual memory management is necessary.

var findAllSubsets = function (elements) {
    elements.sort((x, y) => x - y);
    const result = [];
    const tempSubset = [];
    (function backtrack(result, tempSubset, elements, start) {
        result.push([...tempSubset]);
        for (let i = start; i < elements.length; i++) {
            if (i != start && elements[i] == elements[i - 1]) {
                continue;
            }
            tempSubset.push(elements[i]);
            backtrack(result, tempSubset, elements, i + 1);
            tempSubset.pop();
        }
    })(result, tempSubset, elements, 0);
    return result;
};

The JavaScript implementation provided titled "Subsets II" effectively generates all unique subsets of a given array of numbers. This is achieved by initially sorting the array to facilitate the handling of duplicate elements and then utilizing a backtracking algorithm to explore all potential subsets. Below is a detailed breakdown of how the solution operates:

1. Sorting the Elements: The input array elements is sorted in ascending order. This initial step is crucial as it simplifies the process of skipping over duplicates, ensuring that each subset in the final result is unique.

2. Initiating Variables: Two empty arrays, result and tempSubset, are initialized. The result array will eventually hold all unique subsets, whereas tempSubset is used to build each subset during the recursion.

3. Backtracking Function: A recursive function named backtrack is defined and immediately invoked. This function is designed to generate all possible subsets starting from a given index.

   • It first adds the current tempSubset to the result.
   • The function iterates through the array starting from the start index. If the current element is the same as the one immediately before it and the loop did not just start (controlled by i != start), it skips to the next iteration to prevent adding duplicate subsets.
   • If it is a valid element, the function adds it to tempSubset, recursively calls itself with the next start index (i + 1), and upon return, removes the last element from tempSubset to backtrack and explore other possibilities.

4. Returning the Result: Once the recursion completes, the result containing all unique subsets is returned.

This solution is efficient and effective in handling the complexities associated with duplicates in the input array, ensuring that the subsets included in the final output are unique by leveraging sorting and careful index management during recursion.

class Solution:
    def subsetsWithDuplicates(self, numbers):
        numbers.sort()
        all_subsets = []
        temp_subset = []
        self.findSubsets(all_subsets, temp_subset, numbers, 0)
        return all_subsets
    
    def findSubsets(self, all_subsets, temp_subset, numbers, start):
        all_subsets.append(list(temp_subset))
        for j in range(start, len(numbers)):
            if j > start and numbers[j] == numbers[j - 1]:
                continue
            temp_subset.append(numbers[j])
            self.findSubsets(all_subsets, temp_subset, numbers, j + 1)
            temp_subset.pop()

The code provided is a Python function designed to generate all unique subsets of a list of numbers that may contain duplicates. The function utilizes a backtracking approach to efficiently explore all possible combinations while avoiding duplicate subsets. The process can be broken down as follows:

• Input and Sorting: The main function subsetsWithDuplicates accepts a list of numbers and starts by sorting it. This sorting step is crucial as it allows easy detection of duplicate elements, which helps in avoiding the generation of duplicate subsets.

• Initialization: Two lists, all_subsets to store the final list of subsets, and temp_subset to store the current subset being explored, are initialized.

• Recursive Helper Function: The findSubsets function is a recursive function that builds subsets starting from a provided index start. This function is used to explore all possible subsets by including or excluding each number in the sorted list.

  • It begins by adding a copy of the current temp_subset to all_subsets, capturing the subset formed up to that point.
  • The function loops through the numbers starting from the start index. If a number is the same as the one before it (and is not at the start index), the function skips processing for that number to prevent duplicate subsets.
  • If the current number is not a duplicate (in the context of current recursive path), it is added to temp_subset, and findSubsets is called recursively to continue building the subset from the next index.
  • After the recursive call returns, the last element is removed from temp_subset, effectively backtracking to explore subsets that do not include the current element.

• Return Value: Once all possibilities are explored, all_subsets is returned as the list of all unique subsets.

This method ensures all subsets are considered, and by skipping over duplicates after the first occurrence within the same recursive level, it guarantees that each unique subset is included only once. This is particularly efficient for large datasets with many duplicates, optimizing both time and space complexity by reducing redundant calculations.