using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int[] arr = {1, 2, 3, 4, 5};

        bool[] b = new bool[arr.Length];

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

        int k = 3;

        subset(arr, k, 0, 0, b, result); 

        PrintLists(result);

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

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

        subset2(arr, k, 0, cur, result);

        PrintLists(result);

        result = powerSet(arr, 0);

        PrintLists(result);

    }

    private static void PrintLists(List<List<int>> result){

        Console.WriteLine("-------result--------");

        foreach(List<int> combo in result){

            Console.WriteLine();

            foreach(int i in combo){

                Console.Write(i);   

            }

        }

        Console.WriteLine();

    }

    public static List<List<int>> powerSet(int[] arr, int index){

        List<List<int>> sets;

        if(index == arr.Length)

        {

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

            sets.Add(new List<int>());

            return sets;

        }

        List<List<int>> existingSets = powerSet(arr, index + 1);

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

        sets.AddRange(existingSets);

        foreach(List<int> existingSet in existingSets){

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

            newSet.AddRange(existingSet);

            newSet.Add(arr[index]);

            sets.Add(newSet);

        }

        return sets;

    }

    public static void subset(int[] arr, int k, int start, int length, bool[] used, List<List<int>> result){

        if(length == k){

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

            for(int i = 0; i< arr.Length;i++){

                if(used[i]){

                //  Console.Write(arr[i]);

                    combo.Add(arr[i]);

                }

            }

            result.Add(combo);

            return;

        }

        if(start == arr.Length){

            return ;    

        }

        // For every index we have two options

        // Either we select it, which means true in used[] and increate curIndex

        used[start] = true;

        subset(arr, k, start+1, length + 1, used, result);

        // Or we dont select it, false, and dont increase curIndex

        used[start] = false;

        subset(arr, k, start + 1, length, used, result);

    }

    public static void subset2(int[] arr, int k, int index, List<int> curr, List<List<int>> result){

        if(curr.Count == k){

            result.Add(curr);

            return;

        }

        if(index == arr.Length){

            return ;    

        }

        // For every index we have two options

        // Either we select it

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

        added.AddRange(curr);

        added.Add(arr[index]);

        subset2(arr, k, index+1, added, result);

        // Or we dont select it

        subset2(arr, k, index + 1, curr, result);

    }

}