CareerCup

take the numbers in an array

for (i=0; i<2^n ; i++){
print(i);
}
public void print(int n){
//check all the bits of the number, wherever bit is 1 print that number in the array
}

Simple approach for finding subsets of given set.

#include <stdio.h>
void printAllSet(int *arr, int *aux, int start, int depth, int length)
{
	if(start<= length)
	{
		int i;
		for(i=0;i<depth;i++)
			printf("%d",aux[i]);

		printf("\n");
	}

	int j;
	for(j=start; j<length; j++)
	{

			
			aux[depth] = arr[j];
			printAllSet(arr, aux,start+1, depth+1, length);
			start++;
	}
}
int main()
{
int arr[]={1,2,3,4};
int length=sizeof(arr)/sizeof(arr[0]);
int aux[length];
printAllSet(arr, aux, 0, 0,  length);
return 0;
}

This simple subset generation problem or combination. Are you looking for anything specific in it?

private List<List<Inetger>> powerSet(List<Inetger> numbers) {
      List<List<Inetger>> ps = new ArrayList<List<Integer>>();
      ps.add(new ArrayList<Integer>());

          for (int n : numbers) {
          List<List<Integer>> new_ps = new ArrayList<List<Integer>>();
          for (List<Integer> subset : ps) {
              new_ps.add(subset);
              List<Integer> temp = new ArrayList<Integer>(subset);
              temp.add(n);
              new_ps.add(temp);
          }
          ps = new_ps;
      }
      return ps;
   }

Here is some pseudo-ish code.

for (int i=0; i<2^n; i++) //using n bit number
{
	for(int j=0; j<n; j++)
	{
		if (j th bit of i == 1)
		{
			printf(setasarray[j]);
		}
		printf("\n");
	}
}

Without repetitions, this seems trivial ... O(n^3) ... however, with repetitions, this is more complex .... any good algo for that?

woww even for SDET position they have asked me to write code for same question

Following a complete example using a binary string denoting all
possible combinations:

public static void main(String[] args) {
	    System.out.println("\nPrint all subsets of numbers:");
	    list = new ArrayList<Integer>();
	    list.add(-31);
	    list.add(38);
	    list.add(5);
	    System.out.println(list + "\n");
	    main.printAllSubsSets(list);
	}

	public void printAllSubsSets(List<Integer> list) {
		// 2 ^ list.size() - 1 -> number of possible subsets
		// (and the 'empty' subset)
		Integer maxNumInt = new Integer((int)Math.pow(2, list.size())); 
		String binaryString = null;
		
		for (int i = 1; i < maxNumInt; i++) {
			binaryString = toBinaryString(i, list.size());

			System.out.print(binaryString + " : [");
			for (int j = 0; j < binaryString.length(); j++) {
				if (binaryString.charAt(j) == '1')
					System.out.print(list.get(j) + " ");
			}
			System.out.println("]");			
		}
	}
	
	 private String toBinaryString(int number, int numberOfDigits)   {  
    	StringBuilder result = new StringBuilder(Integer.toBinaryString(number));
    	
        for (int i = result.length(); i < numberOfDigits; i++)
        	result.insert(0, "0");
        
        return result.toString();  
    }

void printAllSubsets(int[] a, int j, int n, string set)
{
    if(j == n)
       print(set + " ");  // add a space at end demarcating end of 1 subset

  for(int i = j;i < n;j++)
  {
      // 2options at each element. either it is part of this   subset or not
      printAllSubsets(a,i+1,n, set+a[i].ToString()); 
      printAllSubsets(a,i+1,n, set);
  }
}

int main()
{
    int[] a = new int[] {1,4,5,67,4,3};
    printAllSubsets(a,0,arr.Length, "");
}

static void printAllSubsets(int[] a)
	{
	    int n = a.length;
	    double upper = Math.pow(2, n);
	    for(int i=0;i<upper;i++)
	    {
	    	//int tmp = i|0;
	    	String value = Integer.toBinaryString(i);
	    	char[] valChar = value.toCharArray();
	    	for(int j=0;j<valChar.length;j++)
	    	{
	    		if(valChar[j] == '1')
	    		{
	    			System.out.print(a[j]);
	    		}
	    	}
	    	System.out.println();
	    }

}

O(2^n)

public class Subsets{
	
	public static void main(String[] args){
		PrintSubsets();
	}
	static void PrintSubsets() 
	{ 
		int[] source = {1,2,3}; 
		int currentSubset = 7; //2^n
		int tmp; 
		while(currentSubset>0) 
		{ 
			System.out.print("("); 
			tmp = currentSubset; 
			for(int i = 0; i<source.length; i++) 
			{ 

				if ((tmp & 1) ==1) 
					System.out.printf("%d ", source[i]); 
				tmp >>= 1; 
			} 
			System.out.printf(")\n"); 
			currentSubset--; 
		} 
	}
}