using System;

using System.Collections.Generic;

public class Program

{

        //Given a set of positive integers, find all its subsets. 

    public static void findSubsets(List<List<int> > subset, List<int> nums, List<int> output, int index)

    {

        // Base Condition

        if (index == nums.Count) {

            subset.Add(output);

            return;

        }

        // Not Including Value which is at Index

        findSubsets(subset, nums, new List<int>(output), index + 1);

        // Including Value which is at Index

        output.Add(nums[index]);

        findSubsets(subset, nums, new List<int>(output), index + 1);

    }

    /* Permutation function @param 

       str string to calculate permutation 

       for @param l starting index @param 

       r end index */

    private static void permute(String str, 

                                int l, int r) 

    { 

        if (l == r) 

            Console.WriteLine(str); 

        else

        { 

            for (int i = l; i <= r; i++) 

            { 

                str = swap(str, l, i); 

                permute(str, l + 1, r); 

                str = swap(str, l, i); 

            } 

        } 

    } 

    /* Swap Characters at position 

       @param a string value @param 

       i position 1 @param j position 2 

       @return swapped string */

    public static String swap(String a, 

                            int i, int j) 

    { 

        char temp; 

        char[] charArray = a.ToCharArray(); 

        temp = charArray[i] ; 

        charArray[i] = charArray[j]; 

        charArray[j] = temp; 

        string s = new string(charArray); 

        return s; 

    } 

​

​

    public static void Main()

    {

        // Main List for storing all subsets

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

        // Input List

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

        input.Add(1);

        input.Add(2);

        input.Add(3);

        findSubsets(subset, input, new List<int>(), 0);

        // Printing Subset

        for (int i = 0; i < subset.Count; i++) {

            for (int j = 0; j < subset[i].Count; j++) {

                Console.Write(subset[i][j] + " ");

            }

            Console.WriteLine();

        }

         String str = "ABC"; 

         int n = str.Length; 

         permute(str, 0, n-1); 

    }

}

​

​

/**

Subsets

Approach: The idea is simple, that if there are n number of elements inside an array, 

there are n number of choices for the first element in the array. Moving forward to the next recursion call, 

there will be n-1 number of choices (as we cannot insert the last element again now) for inserting the second element in the array. 

Using the above idea forms a recursive solution to the problem.

​

Algorithm: 

Create a recursive function that takes the following parameters, input array, the current index, the output array, or current subset, 

if all the subsets need to be stored then a vector of the array is needed if the subsets need to be printed only then this space can be ignored.

First, print the subset (output array) that has been sent to the function and then run a for loop starting from the ‘index’ 

to n-1 where n is the size of the input array. We use a loop to demonstrate that we have exactly n number of choices to choose from when 

adding the first element to our new array. 

Inside the loop, we call the function for the next index after inserting that particular index and then in the next call, we again have (n-1) 

choices to choose from and so it goes. Whenever a call is made for the last index of the array : in that function call, 

the loop is not run as the condition i<A.size() is not fulfilled and hence, 

we backtrack to the last recursion call and call the function for the next index after removing the element at that current index.

​

Complexity Analysis:  

​

Time Complexity: O(n. 2^n). Total number of subsets generated are 2^n, So Time Complexity is O(2^n). If we include the time taken to copy the subset vector into the res vector the time taken will be equal to the size of the subset vector.

Auxiliary Space: O(n) There can be at max n recursion calls at a particular time, which would consume O(n) stack space. 

**/

​

/**

Permutations

​

A permutation also called an “arrangement number” or “order,” is a rearrangement of the elements of an

ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation. 

​

Below are the permutations of string ABC. 

ABC ACB BAC BCA CBA CAB

**/