Subsets Ii

                                            
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> subset;
        sort(nums.begin(), nums.end());
        backtrack(nums, 0, subset, res);
        return res;
    }
    
    void backtrack(vector<int>& nums, int start, vector<int>& subset, vector<vector<int>>& res) {
        res.push_back(subset);
        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            subset.push_back(nums[i]);
            backtrack(nums, i + 1, subset, res);
            subset.pop_back();
        }
    }
};

                                            
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
        result.add(new ArrayList<>(tempList));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

                                            
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        
        def backtrack(start, path):
            res.append(path[:]) # Add a copy of the current path to the result
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i-1]: # Skip duplicates
                    continue
                path.append(nums[i]) # Choose
                backtrack(i + 1, path) # Explore
                path.pop() # Unchoose
            
        nums.sort() # Sort the input array
        backtrack(0, []) # Call the backtrack function starting from index 0 with an empty path
        return res

                                            
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 */
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

void backtrack(int* nums, int numsSize, int start, int* subset, int subsetSize, int** result, int* returnSize, int* returnColumnSizes) {
    result[*returnSize] = (int*)malloc(sizeof(int) * subsetSize);
    memcpy(result[*returnSize], subset, sizeof(int) * subsetSize);
    returnColumnSizes[*returnSize] = subsetSize;
    (*returnSize)++;
    
    for (int i = start; i < numsSize; i++) {
        if (i > start && nums[i] == nums[i-1]) continue;
        subset[subsetSize] = nums[i];
        backtrack(nums, numsSize, i + 1, subset, subsetSize + 1, result, returnSize, returnColumnSizes);
    }
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    // Sort the array to handle duplicates
    qsort(nums, numsSize, sizeof(int), compare);
    
    int** result = (int**)malloc(sizeof(int*) * 2000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    *returnSize = 0;
    
    int subset[2000];
    backtrack(nums, numsSize, 0, subset, 0, result, returnSize, *returnColumnSizes);
    
    return result;
}

                                            
public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums);
        List<IList<int>> result = new List<IList<int>>();
        Backtrack(result, new List<int>(), nums, 0);
        return result;
    }
    
    private void Backtrack(List<IList<int>> result, List<int> tempList, int[] nums, int start) {
        result.Add(new List<int>(tempList));
        for (int i = start; i < nums.Length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            tempList.Add(nums[i]);
            Backtrack(result, tempList, nums, i + 1);
            tempList.RemoveAt(tempList.Count - 1);
        }
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    let res = [];
    
    nums.sort((a, b) => a - b);

    const backtrack = (start, path) => {
        res.push([...path]);
        
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    };
    
    backtrack(0, []);
    
    return res;
};

                                            
function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    
    const result: number[][] = [];
    
    function backtrack(start: number, path: number[]) {
        result.push([...path]);
        
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) {
                continue;
            }
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    
    backtrack(0, []);
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function subsetsWithDup($nums) {
        sort($nums);
        $result = [];
        $this->backtrack($nums, $result, [], 0);
        return $result;
    }
    
    function backtrack($nums, &$result, $current, $start) {
        $result[] = $current;
        
        for ($i = $start; $i < count($nums); $i++) {
            if ($i > $start && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            $current[] = $nums[$i];
            $this->backtrack($nums, $result, $current, $i + 1);
            array_pop($current);
        }
    }
}

                                            
class Solution {
    fun subsetsWithDup(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        nums.sort()
        backtrack(result, ArrayList(), nums, 0)
        return result
    }

    private fun backtrack(result: MutableList<List<Int>>, tempList: ArrayList<Int>, nums: IntArray, start: Int) {
        result.add(ArrayList(tempList))
        for (i in start until nums.size) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue
            }
            tempList.add(nums[i])
            backtrack(result, tempList, nums, i + 1)
            tempList.removeAt(tempList.size - 1)
        }
    }
}

                                            
class Solution {
  List<List<int>> subsetsWithDup(List<int> nums) {
    List<List<int>> result = [];
    List<int> current = [];
    nums.sort();
    
    void backtrack(int index) {
      result.add(List.from(current));
      
      for (int i = index; i < nums.length; i++) {
        if (i > index && nums[i] == nums[i - 1]) {
          continue;
        }
        current.add(nums[i]);
        backtrack(i + 1);
        current.removeLast();
      }
    }
    
    backtrack(0);
    return result;
  }
}

                                            
func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    var path []int
    var backtrack func(start int)

    sort.Ints(nums)

    backtrack = func(start int) {
        temp := make([]int, len(path))
        copy(temp, path)
        res = append(res, temp)

        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0)

    return res
}

                                            
impl Solution {
    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = vec![vec![]];
        let mut nums = nums;
        nums.sort_unstable();
        
        Self::backtrack(&mut result, &mut vec![], &nums, 0);
        
        result
    }
    
    fn backtrack(result: &mut Vec<Vec<i32>>, current: &mut Vec<i32>, nums: &Vec<i32>, start: usize) {
        for i in start..nums.len() {
            if i > start && nums[i] == nums[i-1] {
                continue;
            }
            current.push(nums[i]);
            result.push(current.clone());
            Self::backtrack(result, current, nums, i+1);
            current.pop();
        }
    }
}

                                            
-spec subsets_with_dup(Nums :: [integer()]) -> 
[[integer()]].
subsets_with_dup(Nums) ->
    lists:foldl(
        fun(X, Acc) ->
            lists:usort(Acc ++ lists:map(fun(Set) -> lists:sort([X|Set]) end, Acc))
        end, [[]], lists:sort(Nums)).

To solve this coding challenge, we need to find all unique subsets of a given integer array, which may contain duplicates. The challenge requires us to handle duplicates carefully so that no duplicate subsets are included in the output.

# Explanation

Here's a detailed step-by-step explanation of how to approach this problem:

Sort the Array: Sorting the array helps in managing duplicates efficiently. By sorting, we can easily skip over duplicate numbers during the subset formation process by checking if the current number is equal to the previous number.
Backtracking Approach: We'll use a backtracking approach. This means we will incrementally build all possible subsets by exploring all potential candidates, making a choice, and then exploring further.
Avoid Duplicates: While exploring subsets, we will skip over duplicate elements to ensure that subsets already considered are not included again.
Store Subsets: We'll maintain a result list to store all unique subsets.

# Detailed Steps in Pseudocode

Sort the input array to easily skip duplicates.
Initialize the result list to store all subsets.
Define a backtrack function that takes the current index and path (current subset under construction) as parameters.
Inside the backtrack function :

Add the current path (subset) to the result list.
Iterate over the array starting from the given index to the end.
If the current element is a duplicate (i.e., same as the previous element and not the start of the iteration), skip it.
Otherwise, include the current element in the subset (path), then recursively call the backtrack function for the next element.
After processing, remove the last element from the path to backtrack.

Invoke the backtrack function starting from index 0 with an empty path.
Return the result list containing all unique subsets.

Pseudocode Implementation

                                            
# Sort the input array to handle duplicates.
sort(nums)

# Initialize the result list to store all subsets.
result = []

# Define the backtrack function.
def backtrack(start_index, current_path):
# Add the current subset (copy of current_path) to the result list.
result.append(current_path[:])

# Iterate over the array from the start index to end.
for i in range(start_index, len(nums)):
# Skip duplicates (if current element is same as previous and not the first element in this loop).
if i > start_index and nums[i] == nums[i - 1]:
continue

# Include the current element in the subset (current_path).
current_path.append(nums[i])

# Recursively call backtrack function for the next element.
backtrack(i + 1, current_path)

# Remove the last element from current_path to backtrack.
current_path.pop()

# Call the backtrack function starting from index 0 with an empty path.
backtrack(0, [])

# Return the result list containing all unique subsets.
return result

# Step-by-Step Explanation

Sort the Array: Sorting
nums

enables us to place duplicates next to each other, making it easier to skip over them.
Initialize Result: An empty list
result

is initialized to hold all unique subsets.
Define Backtrack Function:

The function
backtrack(start_index, current_path)

takes the current index (
start_index

) and the subset being built (
current_path

).
Add Subset to Result: The current subset
current_path

is added to
result

.
Loop Over Array: Iterate over elements in
nums

starting from
start_index

. For each element:

Skip Duplicates: If the current element is the same as the previous one and it is not at the start of this loop iteration (checking with
i > start_index

), skip it.
Include Element: Add the current element to
current_path

.
Recurse: Call
backtrack(i + 1, current_path)

to continue building the subset from the next index.
Backtrack: Remove the last element from
current_path

to explore other possibilities.

Invoke and Return: The function
backtrack(0, [])

is called initially with the start index 0 and an empty subset. Finally,
result

is returned, containing all unique subsets.

By following this detailed approach, we ensure that all possible unique subsets of the given array are found and duplicates are effectively handled.