CareerCup

Here's code in C#.

public static void PrintAllCombinationsArray(int[] arr, int k)
        {            
            PrintAllCombinationsArrayPrefix(new int[0], arr, k);
        }
        
        static void PrintAllCombinationsArrayPrefix(int[] prefix, int[] rest, int k)
        {
            if (k == 0)
            {
                PrintArray(prefix);
                return;
            }

            for (int i = 0; i < rest.Length; ++i)
            {
                PrintAllCombinationsArrayPrefix(Add(prefix, rest[i]), Sub(rest, i), k - 1);
            }
        }

        static void PrintArray(int[] arr)
        {
            foreach (int i in arr)
                Console.Write(i + " ");
            Console.WriteLine();
        }

        static int[] Add(int[] prefix, int x)
        {            
            int[] foo = new int[prefix.Length + 1];
            for (int i = 0; i < prefix.Length; ++i)
                foo[i] = prefix[i];
            foo[prefix.Length] = x;
            return foo;
        }

        static int[] Sub(int[] prefix, int x)
        {
            int[] foo = new int[prefix.Length - 1];
            for (int i = 0; i < x; i++)
                foo[i] = prefix[i];
            for (int i = x + 1; i < prefix.Length; i++)
                foo[i-1] = prefix[i];
            
            return foo;
        }

Two solutions, one with complexity 2^n and the other with n!

Soln 1:
//input
arr[]
k

vector<set<string> > s;

void generateSets(set<int> v,int n,int ind) {
	if(n == k) {
		s.push_back(v);
	}
	if(ind == v.size()) return;
	else {
		generateSets(v,n+1,ind+1);
		v.insert(arr[ind])
		generateSets(v,n+1,ind+1);
	}
}
//method call
generateSets(new set<int>(),0,0);

Soln 2:
//input
vector<int> arr
k

vector<set<int> > generateSets() {
	sort(arr.begin(),arr.end());
	set<int> s;
	do { 
		for(int i=0;i<k;i++) {
			v.insert(arr[i]);
		}
		s.push_back(v);
	} while(next_permutation(arr.begin(),arr.end()));
	
}

for(int i=0; i<(1<<n); i++){
        vector<int> subset;
        for(int j=0; j<n; j++){
            if((i & (1<<j)) > 0) {
                subset.push_back(a[j]);
            }
        }
        
        if(subset.size() == k) {
              // print the subset or return
        }
    }

#define SUBSET_LENGTH 3

void generateSubset(int array[], int subset[], int used[], int length, int index, int lastoffset)
{
int k;

if (index == SUBSET_LENGTH)
{
printf("subset %d%d%d\n", subset[0], subset[1], subset[2]);
return;
}

for (k = 0; k < length; k++)
{
if (used[k]) continue;
if (k < lastoffset) continue;
subset[index] = array[k];
used[k] = 1;
generateSubset(array, subset, used, length, index + 1, k);
used[k] = 0;
}
}

int main()
{
int array[4] = {1, 2, 3, 4};
int used[4];
int subset[SUBSET_LENGTH];

memset((void *)used, 0, sizeof(array)/sizeof(int));
memset((void *)subset, 0, SUBSET_LENGTH);

generateSubset(array, subset, used, sizeof(array)/sizeof(int), 0, 0);

return 0;
}

please anyone explain above code?

The above code is similar to the DFS algorithm.
But, this code will not work for input that has duplicate entry like (1 1 2 6 8)

#include<stdio.h>
int temp[3] = {0,0,0};
int arr[] = {1,2,3,4,5};
void rec( int k , int j)
{
int i;
if(k == 3)
{
printf("%d %d %d\n",temp[0],temp[1],temp[2]);
return;
}
for(i = j; i < 5;i++)
{
temp[k] = arr[i];
rec(k+1,i + 1);
}
}

void main()
{
rec(0,0);
getchar();
}

what to do..

Each number between [0 and 2^n) in its bit form corresponds to which elements to include from array and which to exclude.

Generate those subsets whose corresponding bit vector has k number of 1s.

//Given an array, this function finds the startIdx of subset array of size k
// The indices are stored in the startId vector
// Recursively call
void FindSubset(int curPos, int k, int arraySize, vector<int>& startId)
{
if(curPos+k > arraySize)
return;
startId.push_back(curPos);
curPos++;
FindSubset(curPos, k, arraySize, startId);
}

int main ()
{
vector<int> startId;
int k = 4;
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
FindSubset(0, k, 10, startId);
int sizeSubSets = startId.size();
cout << "total subsets found:" << sizeSubSets << endl;
for(int i=0; i < sizeSubSets; i++)
{
int currPos = startId[i];
cout << "SubsetArray= {";
for(int j=currPos; j < currPos+k; j++)
{
cout << arr[j] << " ";
}
cout << "}" << endl;
}
return 0;
}

The simplest way is to think recursively..

method signature : allsubets(int[] input, i, k);


here i denotes the starting index of the input array to consider and k denotes the size of subsets to generate.

subsets_1 = allsubset(input, i+1, k-1) /* use i. */
for (subset s : subsets_1)
add input[i] to s

subsets_2 = allsubsets(input, i+1, k-1) /* don't use i */

return combine(subsets_1, subsets_2);

Note: not handling trivial case. Its easy enough.
Also we can easily memoize this.

#include <stdio.h>

void subarray(int arr[], int t[], int n, int ind, int k, int kk) {
int i;
if (n == 0)
return;
if (kk == k) {
for (i = 0; i < kk; i++)
printf("%d ", t[i]);
printf("\n");
return;
}
if (n - ind < k - kk)
return;
t[kk] = arr[ind];
subarray(arr, t, n, ind + 1, k, kk + 1);
subarray(arr, t, n, ind + 1, k, kk);
}


int main() {
int i, arr[100], t[100], n, k;
do {
printf("Enter array size:");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", arr + i);
printf("Enter sub-array-size:");
scanf("%d", &k);
subarray(arr, t, n, 0, k, 0);
} while(n);

}

a simple python solution

cur=[]
count=0
Arr=[...some stuff...]

def ss2(n,k):
    global count
    count+=1
    if k==0:
        print cur # maybe cur is the index of Arr
        return 
    for i in range(k-1,n):
        cur.append(i)
        ss2(i,k-1)
        cur.pop()

ss2(10,3) 
print count # for time complexity

a simple python solution

cur=[]
count=0
Arr=[...some stuff...]

def ss2(n,k):
    global count
    count+=1
    if k==0:
        print cur # maybe cur is the index of Arr
        return 
    for i in range(k-1,n):
        cur.append(i)
        ss2(i,k-1)
        cur.pop()

ss2(10,3) 
print count # for time complexity

public class Set {
int[] elem;
int size;
Set(int n) {
elem = new int[n];
}

public Set clone() {
Set temp = new Set(elem.length);
int[] clonedElem = elem.clone();
int clonedSize = size;
temp.elem = clonedElem;
temp.size = clonedSize;

return temp;
}
public void add(int n) {
elem[size]=n;
size++;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("{");
for(int i=0;i<size;i++) {
sb.append(elem[i]);
sb.append(",");
}
sb.append("}");
return sb.toString();
}

}
public List<Set> setsOfSizeK(int[] a,int index, int k, Set s) {
List<Set> ls=new ArrayList<Set>();

for(int i=index;i<=a.length;i++) {
if(k>0 && i< a.length) {
Set temp = s.clone();
temp.add(a[i]);
List<Set> res = setsOfSizeK(a,i+1,k-1,temp);
if(!res.isEmpty())
ls.addAll(res);
} else if(k==0 && i<= a.length) {
ls.add(s);
break;
}

}


return ls;

}

@Test
public void testSetsOfSizeK() {
int[] a = {1,2,3,4};
List<Set> l = setsOfSizeK(a,0,2,new Set(2));
System.out.print(l.size());
}

am i understand the problem in a wrong way?

set<int> full(all(vals));
for (auto it = full.begin(); it != full.end(); it++)
for (auto it2 = ++it--; it2 != full.end(); it2++)
for (auto it3 = ++it2--; it3 != full.end(); it3++)
cout << *it << ' ' << *it2 << ' ' << *it3 << endl;

I think it can be done in O(kn) where k is subarray size and n is the given array size.

Let A be the array of numbers with size n.
Let C be an array such that C[i,j] contains the possible subsets of size j from array A with size i.
We want C[n,k]. We will find it by Dynamic Programming using Memoized version.
Here is the algorithm:

SET(A,n,k)
for i<-1 to n
f
C[i,1]={A[i]}
for j<-1 to n
for i<-1 to k
C[j,i]=empty set
return MEMOIZED(A,C,n,k)



MEMOIZED(A,C,n,k)
if k=0 or n=0
C[n,k]=empty set
else if k=1 and C[n,k]=empty set
for j<-1 to n
C[n,k]=C[n,k] U {A[j]}// here U adds subset {A[j]} to set of subsets in C[n,k]
return C[n,k]
if n<k
return C[n,k]
if n=k
C[n,k]= MEMOIZED(A,C,n-1,k-1) U A[n] //here U will add A[n] to every subset in C[n-1,k-1]
else
C[n,k]= MEMOIZED(A,C,n-1,k) U (MEMOIZED(A,C,n-1,k-1) U A[n])
return C[n,k]


Clearly we reach each box in array C only once .So Time Complexity is O(kn)

Solution in C#:

using System;
using System.Collections.Generic;

public class Program
{
    public static List<List<int>> sets = new List<List<int>>();

    public static void FindSubsets(int[] superSet, int K)
    {
        FindSubsets(superSet, K, 0, new List<int>());
    }

    private static void FindSubsets(int[] superSet, int K, int index, List<int> set)
    {
        if (set.Count == K)
        {
            sets.Add(new List<int>(set));
            return;
        }
        if (index == superSet.Length) return;

        int num = superSet[index];
        set.Add(num);
        FindSubsets(superSet, K, index + 1, set);
        set.Remove(num);
        FindSubsets(superSet, K, index + 1, set);
    }

    public static void Main()
    {
        var nums = new int[] { 1, 2, 3, 4, 5, 6 };
        FindSubsets(nums, 3);
        foreach(var set in sets) 
        {
            foreach (var num in set) Console.Write(num);
            Console.WriteLine();
        }
        Console.ReadLine();
    }
}