// Solutions for: https://leetcode.com/problems/subsets/description/

using System;

using System.Collections.Generic;                   

public class Program

{

    public void Main()

    {

        IList<IList<int>> ps = new List<IList<int>>(){new List<int>()};

        int[] nums = {1, 2, 3};

        ps = Subsets(nums);

        foreach(var i in ps)

        {

            foreach(var j in i)

            {

                Console.Write(j);               

            }

            Console.WriteLine();

        }

    }

    public IList<IList<int>> powerset = new List<IList<int>>();

    public Stack<int> visited = new Stack<int>();

    public IList<IList<int>> Subsets(int[] nums) {

​

        Backtrack(nums, 0);

        return powerset;

    }

    public void Backtrack(int[] nums, int start)

    {

        List<int> backtracked = new List<int>();

        foreach(int i in visited.ToArray())

        {

            backtracked.Add(i);

        }

        powerset.Add(backtracked);

        for(int i = start; i < nums.Length; i++)

        {

            visited.Push(nums[i]);

            Backtrack(nums, i+1);            

            visited.Pop();

        }

    }

​

}