Subsets

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

                                            
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generateSubsets(nums, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        
        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);
            generateSubsets(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

                                            
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(start, path, result):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path, result)
                path.pop()
        
        result = []
        backtrack(0, [], result)
        return result

                                            
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 */
int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    // Calculate the number of subsets
    int numSubsets = pow(2, numsSize);
    
    // Allocate memory for the result arrays
    int **result = (int **)malloc(sizeof(int *) * numSubsets);
    *returnColumnSizes = (int *)malloc(sizeof(int) * numSubsets);
    *returnSize = numSubsets;
    
    // Generate the subsets
    for (int i = 0; i < numSubsets; i++) {
        int subsetSize = 0;
        result[i] = (int *)malloc(sizeof(int) * numsSize);
        
        for (int j = 0; j < numsSize; j++) {
            if (i & (1 << j)) {
                result[i][subsetSize] = nums[j];
                subsetSize++;
            }
        }
        
        (*returnColumnSizes)[i] = subsetSize;
    }
    
    return result;
}

                                            
public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        GenerateSubsets(nums, 0, current, result);
        return result;
    }

    private void GenerateSubsets(int[] nums, int index, List<int> current, IList<IList<int>> result)
    {
        result.Add(new List<int>(current));
        for (int i = index; i < nums.Length; i++)
        {
            current.Add(nums[i]);
            GenerateSubsets(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const result = [[]];
    
    for (let num of nums) {
        const n = result.length;
        for (let i = 0; i < n; i++) {
            const subset = result[i].slice();
            subset.push(num);
            result.push(subset);
        }
    }
    
    return result;
};

                                            
function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const backtrack = (start: number, curr: number[]) => {
        result.push(curr.slice());
        for (let i = start; i < nums.length; i++) {
            curr.push(nums[i]);
            backtrack(i + 1, curr);
            curr.pop();
        }
    };
    backtrack(0, []);
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function subsets($nums) {
        $output = [[]];
        foreach ($nums as $num) {
            foreach ($output as $curr) {
                $output[] = array_merge($curr, [$num]);
            }
        }
        return $output;
    }
}

                                            
class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var subset: [Int] = []

        backtrack(&result, &subset, nums, 0)

        return result
    }

    func backtrack(_ result: inout [[Int]], _ subset: inout [Int], _ nums: [Int], _ index: Int) {
        result.append(subset)

        for i in index..<nums.count {
            subset.append(nums[i])
            backtrack(&result, &subset, nums, i + 1)
            subset.removeLast()
        }
    }
}

                                            
class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        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) {
            tempList.add(nums[i])
            backtrack(result, tempList, nums, i + 1)
            tempList.removeAt(tempList.size - 1)
        }
    }
}

                                            
class Solution {
  List<List<int>> subsets(List<int> nums) {
    List<List<int>> result = [];
    
    void backtrack(int start, List<int> path) {
      result.add(List.from(path));
      
      for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(i + 1, path);
        path.removeLast();
      }
    }
    
    backtrack(0, []);
    
    return result;
  }
}

                                            
func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    subset := make([]int, 0)

    var backtrack func(start int)
    backtrack = func(start int) {
        temp := make([]int, len(subset))
        copy(temp, subset)
        result = append(result, temp)

        for i := start; i < len(nums); i++ {
            subset = append(subset, nums[i])
            backtrack(i + 1)
            subset = subset[:len(subset)-1]
        }
    }

    backtrack(0)

    return result
}

                                            
# @param {Integer[]} nums
# @return {Integer[][]}
def subsets(nums)
    result = []
    
    (0..nums.length).each do |i|
        nums.combination(i).each do |subset|
            result << subset
        end
    end
    
    result
end

                                            
object Solution {
    def subsets(nums: Array[Int]): List[List[Int]] = {
        def backtrack(start: Int, path: List[Int]): List[List[Int]] = {
            if (start == nums.length) {
                List(path)
            } else {
                backtrack(start + 1, path) ++ backtrack(start + 1, nums(start) :: path)
            }
        }
        
        backtrack(0, List())
    }
}

                                            
impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        let n = nums.len();
        
        for i in 0..1 << n {
            let mut subset = Vec::new();
            for j in 0..n {
                if (i >> j) & 1 == 1 {
                    subset.push(nums[j]);
                }
            }
            res.push(subset);
        }
        
        res
    }
}

                                            
-spec subsets(Nums :: [integer()]) -> [[integer()]].
subsets(Nums) ->
    Results = [[]],
    lists:foldl(
        fun(X, Acc) -> 
            lists:append(lists:map(fun(Y) -> [X | Y] end, Acc), Acc)
        end,
        Results,
        Nums
    ).

To solve this coding challenge, we need to generate all possible subsets (the power set) of a given array of unique integers. The methodology we'll use involves a backtracking algorithm, which is suitable for problems requiring exploration of all possible combinations.

# Explanation

The problem is to find all subsets of a provided list of unique integers. A subset is defined as any combination of elements from the list, including the empty set and the set containing all elements. The goal is to ensure that all possible combinations are covered without any duplications. In order to generate these subsets, a powerful and intuitive method is backtracking . Here is a detailed explanation of how backtracking works for this problem:

Initialization : Start with an empty subset and gradually build it by adding one element at a time from the original list.
Recursive Exploration : Use a recursive function to try and include/exclude each element of the list. Once all elements have been considered, the current subset is stored.
Backtrack : At each stage, after recursively exploring one possibility, step back (backtrack) by removing the last considered element and explore the next possibility.

# Detailed Steps in Pseudocode:

Base Case Consideration : Start by acknowledging that the empty set is a subset.
Backtracking Function :

If
start

is the current index in the array, we will iterate from
start

to the end of the array.
For each element in the array, add it to the current subset
path

.
Call backtracking function recursively with the updated
start

and
path

.
After recursion, remove the last element added to
path

to backtrack.

Final Compilation : Collect all the subsets generated during the recursive process.

# Pseudocode with Comments:

                                            
# Function to generate all subsets (power set)
# Define a backtrack function for recursive exploration

# Starting point for generating subsets 
# 'start' is the index in the array we're considering
# 'current_subset' stores the current subset being built
# 'all_subsets' stores all the subsets we've found so far

function backtrack(start, current_subset, all_subsets):
# Append a copy of the current subset to the results
add copy of current_subset to all_subsets

# Iterate over possible next elements in the array
for i from start to length of nums - 1 do:
# Add the current element to the current subset
append nums[i] to current_subset

# Recurse with the updated state (moving the start index ahead)
backtrack(i + 1, current_subset, all_subsets)

# Remove the last element added to current_subset
# This is backtracking to try the next possible subset
remove last element from current_subset

# Main function to handle the subset generation
function subsets(nums):
# List to store all subsets
result = empty list

# Begin backtracking with an empty subset
backtrack(0, empty list, result)

# Return the complete list of subsets
return result

# Step-by-Step Explanation:

Initialization :

The main
subsets

function initializes a list
result

which will eventually hold all the subsets.
The initial call to
backtrack

starts with an empty list for
current_subset

and with the starting index
0

.

Base Case & Copying the Subset :

Each time the function is called, it appends a copy of
current_subset

to
result

.
Initially, this means the empty list
[]

is added to
result

.

Iterate and Recurse :

A
for

loop iterates through the elements in
nums

starting from the index
start

.
For each iteration, the current element is added to
current_subset

.
backtrack

is called recursively with the next starting index and the updated
current_subset

.

Backtracking :

After the recursive call completes, the last added element is removed from
current_subset

. This step is crucial as it allows exploring other combinations by resetting the state.

Completion :

Once backtracking has generated all possible subsets,
result

containing all subsets is returned.

By following this structured backtracking methodology, we comprehensively and efficiently explore all possible subsets of the array, ensuring no duplicates and covering all combinations.