subject

Given a set of integer arrays nums without repeating elements, all possible subsets (power sets) of the array are returned.

Description: Unset cannot contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Algorithm implementation

public IList<IList<int>> Subsets(int[] nums)
{
    IList<IList<int>> list = new List<IList<int>>();
    list.Add(new List<int>());
    int len;
    for (int i = 0; i < nums.Length; i++)
    {
        len = list.Count;//Record the number of elements to copy
        for (int j = 0; j < len; j++)//Replicated subset
        {
            list.Add(new List<int>(list[j]));
        }
        for (int k = len; k < list.Count; k++)//Add the current element to the subset replicated later
        {
            list[k].Add(nums[i]);
        }
    }
    return list;
}

results of enforcement

Implementation results: through
Execution time: 368 ms, beating 72.22% of all C# submissions
Memory consumption: 29.6 MB, beating 6.67% of users in all C 񖓿 submissions

Small summary

This problem is a little difficult for me. I intend to find the law first, but failed. Later, when I read the problem, I learned a recursive method. I can understand it and compile my own program. The latter backtracking method has been successfully transplanted to c #, but it is a little unknown.

Backtracking method

//Backtracking method
private IList<IList<int>> res;
private void find(int[] nums, int begin, IList<int> pre)
{
    // No explicit recursive termination
    res.Add(new List<int>(pre));// Note: Here's a new one.
    for (int i = begin; i < nums.Length; i++)
    {
        pre.Add(nums[i]);
        find(nums, i + 1, pre);
        pre.RemoveAt(pre.Count - 1);// Combination problem, state reset after recursion
    }
}
public IList<IList<int>> Subsets(int[] nums)
{
    int len = nums.Length;
    res = new List<IList<int>>();
    if (len == 0)
    {
        return res;
    }
    IList<int> pre = new List<int>();
    find(nums, 0, pre);
    return res;
}