CareerCup

Sort the array. Then, code the usual recursive powerset implementation, but with some changes: each call will first recursively compute the powerset without the current element. Then, iterate from the current index and keep incrementing until a different element is found. Now, recurse with 1 element, 2 equal elements, 3 equal elements, etc., but passing the index of the first different element to the next call.

Here's a working implementation in C++:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static void powerset_aux(const vector<int> &elems, vector<int>::size_type elems_i, vector<int> &out_buff) {
	if (elems_i >= elems.size()) {
		cout << "{ ";
		if (out_buff.size() > 0) {
			cout << out_buff[0];
		}
		for (vector<int>::size_type i = 1; i < out_buff.size(); i++) {
			cout << ", " << out_buff[i];
		}
		cout << " }" << endl;
		return;
	}

	vector<int>::size_type next_different;
	for (next_different = elems_i+1;
	     next_different < elems.size() && elems[next_different] == elems[elems_i];
	     next_different++)
		; /* Intentionally left blank */

	powerset_aux(elems, next_different, out_buff);

	for (vector<int>::size_type next_eq = elems_i; next_eq != next_different; next_eq++) {
		out_buff.push_back(elems[next_eq]);
		powerset_aux(elems, next_different, out_buff);
	}

	for (vector<int>::size_type i = elems_i; i != next_different; i++) {
		out_buff.pop_back();
	}
}

void powerset(vector<int> &elems) {

	sort(elems.begin(), elems.end());

	vector<int> buff;
	powerset_aux(elems, 0, buff);
}

int main(void) {
	cout << "Enter the number of elements, followed by each element, to generate the power set." << endl;
	cout << "> ";

	vector<int>::size_type elems_no;
	while (cin >> elems_no) {
		vector<int> elems;
		for (vector<int>::size_type i = 0; i < elems_no; i++) {
			int element;
			cin >> element;
			elems.push_back(element);
		}
		powerset(elems);
		cout << "> ";
	}

	return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class Combinatorics {

	private static class Node{
		int lastIndex = 0;
		List<Integer> currentList;
		public Node(int lastIndex, List<Integer> list) {
			this.lastIndex = lastIndex;
			this.currentList = list;
		}
		public Node(Node n) {
			this.lastIndex = n.lastIndex;
			this.currentList = new ArrayList<Integer>(n.currentList);
		}
	}
	public List<List<Integer> > findAllCombinations(int [] input) {
		List<List<Integer>> resultList = new ArrayList<List<Integer>>();
		LinkedList<Node> queue = new LinkedList<Node>();
		int n = input.length;
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(input[0]);
		queue.add(new Node(0, temp));
		// add all different integers to the queue once.
		for(int i=1;i<n;++i) {
			if(input[i-1] == input[i]) continue;
			temp = new ArrayList<Integer>();
			temp.add(input[i]);
			queue.add(new Node(i, temp));
		}
		// do bfs until we have no elements
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			if(node.lastIndex+1 < n) {
				Node newNode = new Node(node);
				newNode.lastIndex = node.lastIndex+1;
				newNode.currentList.add(input[node.lastIndex+1]);
				queue.add(newNode);
			}
			for(int i=node.lastIndex+2;i<n;++i) {
				if(input[i-1] == input[i]) continue;
				// create a copy and add extra integer
				Node newNode = new Node(node);
				newNode.lastIndex = i;
				newNode.currentList.add(input[i]);
				queue.add(newNode);
			}
			resultList.add(node.currentList);
		}
		return resultList;
	}
}

Java implementation.
Assumption input array is sorted.
Basic idea is to start with single set unique elements and keep on adding on them using BFS.
1) Find all unique arrays and add it in the queue
2) Until the queue is empty, pick each one out and add next item in the array which is not already added.
3) Add all the generated lists into the result list.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class Combinatorics {

	private static class Node{
		int lastIndex = 0;
		List<Integer> currentList;
		public Node(int lastIndex, List<Integer> list) {
			this.lastIndex = lastIndex;
			this.currentList = list;
		}
		public Node(Node n) {
			this.lastIndex = n.lastIndex;
			this.currentList = new ArrayList<Integer>(n.currentList);
		}
	}
	public List<List<Integer> > findAllCombinations(int [] input) {
		List<List<Integer>> resultList = new ArrayList<List<Integer>>();
		LinkedList<Node> queue = new LinkedList<Node>();
		int n = input.length;
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(input[0]);
		queue.add(new Node(0, temp));
		// add all different integers to the queue once.
		for(int i=1;i<n;++i) {
			if(input[i-1] == input[i]) continue;
			temp = new ArrayList<Integer>();
			temp.add(input[i]);
			queue.add(new Node(i, temp));
		}
		// do bfs until we have no elements
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			if(node.lastIndex+1 < n) {
				Node newNode = new Node(node);
				newNode.lastIndex = node.lastIndex+1;
				newNode.currentList.add(input[node.lastIndex+1]);
				queue.add(newNode);
			}
			for(int i=node.lastIndex+2;i<n;++i) {
				if(input[i-1] == input[i]) continue;
				// create a copy and add extra integer
				Node newNode = new Node(node);
				newNode.lastIndex = i;
				newNode.currentList.add(input[i]);
				queue.add(newNode);
			}
			resultList.add(node.currentList);
		}
		return resultList;
	}
}

Java implementation.
Assumption input array is sorted.
Basic idea is to start with single set unique elements and keep on adding on them using BFS.
1) Find all unique arrays and add it in the queue
2) Until the queue is empty, pick each one out and add next item in the array which is not already added.
3) Add all the generated lists into the result list.

public class Combinatorics {

	private static class Node{
		int lastIndex = 0;
		List<Integer> currentList;
		public Node(int lastIndex, List<Integer> list) {
			this.lastIndex = lastIndex;
			this.currentList = list;
		}
		public Node(Node n) {
			this.lastIndex = n.lastIndex;
			this.currentList = new ArrayList<Integer>(n.currentList);
		}
	}
	public List<List<Integer> > findAllCombinations(int [] input) {
		List<List<Integer>> resultList = new ArrayList<List<Integer>>();
		LinkedList<Node> queue = new LinkedList<Node>();
		int n = input.length;
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(input[0]);
		queue.add(new Node(0, temp));
		// add all different integers to the queue once.
		for(int i=1;i<n;++i) {
			if(input[i-1] == input[i]) continue;
			temp = new ArrayList<Integer>();
			temp.add(input[i]);
			queue.add(new Node(i, temp));
		}
		// do bfs until we have no elements
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			if(node.lastIndex+1 < n) {
				Node newNode = new Node(node);
				newNode.lastIndex = node.lastIndex+1;
				newNode.currentList.add(input[node.lastIndex+1]);
				queue.add(newNode);
			}
			for(int i=node.lastIndex+2;i<n;++i) {
				if(input[i-1] == input[i]) continue;
				// create a copy and add extra integer
				Node newNode = new Node(node);
				newNode.lastIndex = i;
				newNode.currentList.add(input[i]);
				queue.add(newNode);
			}
			resultList.add(node.currentList);
		}
		return resultList;
	}
}

Here is the code in Java
Assumption input is sorted
Basic idea is to do BFS
1) First find all unique list of integers of size 1. Push this onto queue
2) Keep adding new elements on the right until we cant add anymore

public class Combinatorics {

	private static class Node{
		int lastIndex = 0;
		List<Integer> currentList;
		public Node(int lastIndex, List<Integer> list) {
			this.lastIndex = lastIndex;
			this.currentList = list;
		}
		public Node(Node n) {
			this.lastIndex = n.lastIndex;
			this.currentList = new ArrayList<Integer>(n.currentList);
		}
	}
	public List<List<Integer> > findAllCombinations(int [] input) {
		List<List<Integer>> resultList = new ArrayList<List<Integer>>();
		LinkedList<Node> queue = new LinkedList<Node>();
		int n = input.length;
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(input[0]);
		queue.add(new Node(0, temp));
		// add all different integers to the queue once.
		for(int i=1;i<n;++i) {
			if(input[i-1] == input[i]) continue;
			temp = new ArrayList<Integer>();
			temp.add(input[i]);
			queue.add(new Node(i, temp));
		}
		// do bfs until we have no elements
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			if(node.lastIndex+1 < n) {
				Node newNode = new Node(node);
				newNode.lastIndex = node.lastIndex+1;
				newNode.currentList.add(input[node.lastIndex+1]);
				queue.add(newNode);
			}
			for(int i=node.lastIndex+2;i<n;++i) {
				if(input[i-1] == input[i]) continue;
				// create a copy and add extra integer
				Node newNode = new Node(node);
				newNode.lastIndex = i;
				newNode.currentList.add(input[i]);
				queue.add(newNode);
			}
			resultList.add(node.currentList);
		}
		return resultList;
	}
}

Here is the code in Java
Assumption input is sorted
Basic idea is to do BFS
1) First find all unique list of integers of size 1. Push this onto queue
2) Keep adding new elements on the right until we cant add anymore

public class Combinatorics {

	private static class Node{
		int lastIndex = 0;
		List<Integer> currentList;
		public Node(int lastIndex, List<Integer> list) {
			this.lastIndex = lastIndex;
			this.currentList = list;
		}
		public Node(Node n) {
			this.lastIndex = n.lastIndex;
			this.currentList = new ArrayList<Integer>(n.currentList);
		}
	}
	public List<List<Integer> > findAllCombinations(int [] input) {
		List<List<Integer>> resultList = new ArrayList<List<Integer>>();
		LinkedList<Node> queue = new LinkedList<Node>();
		int n = input.length;
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(input[0]);
		queue.add(new Node(0, temp));
		// add all different integers to the queue once.
		for(int i=1;i<n;++i) {
			if(input[i-1] == input[i]) continue;
			temp = new ArrayList<Integer>();
			temp.add(input[i]);
			queue.add(new Node(i, temp));
		}
		// do bfs until we have no elements
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			if(node.lastIndex+1 < n) {
				Node newNode = new Node(node);
				newNode.lastIndex = node.lastIndex+1;
				newNode.currentList.add(input[node.lastIndex+1]);
				queue.add(newNode);
			}
			for(int i=node.lastIndex+2;i<n;++i) {
				if(input[i-1] == input[i]) continue;
				// create a copy and add extra integer
				Node newNode = new Node(node);
				newNode.lastIndex = i;
				newNode.currentList.add(input[i]);
				queue.add(newNode);
			}
			resultList.add(node.currentList);
		}
		return resultList;
	}
}

Here is the code in Java
Assumption input is sorted
Basic idea is to do BFS
1) First find all unique list of integers of size 1. Push this onto queue
2) Keep adding new elements on the right until we cant add anymore

public class NumberCombinations {
public static void main(String[] args) {
int[] numbers = {1, 1, 2, 3};
Set<Integer> set = new HashSet<Integer>();
List<Integer> list = null;
for (int n = 0; n < numbers.length; n++) {
StringBuilder sb;
list = new ArrayList<Integer>();
list.add(numbers[n]);
set.add(numbers[n]);
for (int m = n+1; m < numbers.length; m++) {
sb = new StringBuilder();
list.add(numbers[m]);
Collections.sort(list);
for (Integer num : list) {sb.append(num);}
set.add(Integer.parseInt(sb.toString()));
}
for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
sb = new StringBuilder();
list.add(numbers[m]);
Collections.sort(list);
for (Integer num : list) {sb.append(num);}
set.add(Integer.parseInt(sb.toString()));
}
}
System.out.println(getFormattedOutput(set));
}
private static String getFormattedOutput(Set<Integer> set){
String finalNumbers = "";
List<Integer> list = new ArrayList<Integer>();
list.addAll(set);
Collections.sort(list);
List<String> finalList = new ArrayList<String>();
for (Integer num : list) {
String st = num.toString();
if(st.length() == 1 ){
finalList.add("{"+num+"}");
}else{
String st1 = "{";
for (int i = 0; i < st.length(); i++) {
if(st.length() -1 == i){
st1 = st1+st.charAt(i);
}else{
st1 = st1+st.charAt(i)+" ";
}
}
finalList.add(st1+"}");
}
}
finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
return finalNumbers;
}
}

public class NumberCombinations {
	public static void main(String[] args) {
		int[] numbers = {1, 1, 2, 3};
		Set<Integer> set = new HashSet<Integer>();
		List<Integer> list = null;
		for (int n = 0; n < numbers.length; n++) {
			StringBuilder sb;
			list = new ArrayList<Integer>();
			list.add(numbers[n]);
			set.add(numbers[n]);
			for (int m = n+1; m < numbers.length; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}
			for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}	
		}
		System.out.println(getFormattedOutput(set));
	}
	private static String getFormattedOutput(Set<Integer> set){
		String finalNumbers = "";
		List<Integer> list = new ArrayList<Integer>();
		list.addAll(set);
		Collections.sort(list);
		List<String> finalList = new ArrayList<String>();
		for (Integer num : list) {
			String st = num.toString();
			if(st.length() == 1 ){
				finalList.add("{"+num+"}");
			}else{
				String st1 = "{";
				for (int i = 0; i < st.length(); i++) {
					if(st.length() -1 == i){
						st1 = st1+st.charAt(i);
					}else{
						st1 = st1+st.charAt(i)+" ";
					}
				}
				finalList.add(st1+"}");
			}
		}
		finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
		return finalNumbers;
	}

}

public class NumberCombinations {
	public static void main(String[] args) {
		int[] numbers = {1, 1, 2, 3};
		Set<Integer> set = new HashSet<Integer>();
		List<Integer> list = null;
		for (int n = 0; n < numbers.length; n++) {
			StringBuilder sb;
			list = new ArrayList<Integer>();
			list.add(numbers[n]);
			set.add(numbers[n]);
			for (int m = n+1; m < numbers.length; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}
			for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}	
		}
		System.out.println(getFormattedOutput(set));
	}
	private static String getFormattedOutput(Set<Integer> set){
		String finalNumbers = "";
		List<Integer> list = new ArrayList<Integer>();
		list.addAll(set);
		Collections.sort(list);
		List<String> finalList = new ArrayList<String>();
		for (Integer num : list) {
			String st = num.toString();
			if(st.length() == 1 ){
				finalList.add("{"+num+"}");
			}else{
				String st1 = "{";
				for (int i = 0; i < st.length(); i++) {
					if(st.length() -1 == i){
						st1 = st1+st.charAt(i);
					}else{
						st1 = st1+st.charAt(i)+" ";
					}
				}
				finalList.add(st1+"}");
			}
		}
		finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
		return finalNumbers;
	}

}

public class NumberCombinations {
	public static void main(String[] args) {
		int[] numbers = {1, 1, 2, 3};
		Set<Integer> set = new HashSet<Integer>();
		List<Integer> list = null;
		for (int n = 0; n < numbers.length; n++) {
			StringBuilder sb;
			list = new ArrayList<Integer>();
			list.add(numbers[n]);
			set.add(numbers[n]);
			for (int m = n+1; m < numbers.length; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}
			for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}	
		}
		System.out.println(getFormattedOutput(set));
	}
	private static String getFormattedOutput(Set<Integer> set){
		String finalNumbers = "";
		List<Integer> list = new ArrayList<Integer>();
		list.addAll(set);
		Collections.sort(list);
		List<String> finalList = new ArrayList<String>();
		for (Integer num : list) {
			String st = num.toString();
			if(st.length() == 1 ){
				finalList.add("{"+num+"}");
			}else{
				String st1 = "{";
				for (int i = 0; i < st.length(); i++) {
					if(st.length() -1 == i){
						st1 = st1+st.charAt(i);
					}else{
						st1 = st1+st.charAt(i)+" ";
					}
				}
				finalList.add(st1+"}");
			}
		}
		finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
		return finalNumbers;
	}

}

public class NumberCombinations {
	public static void main(String[] args) {
		int[] numbers = {1, 1, 2, 3};
		Set<Integer> set = new HashSet<Integer>();
		List<Integer> list = null;
		for (int n = 0; n < numbers.length; n++) {
			StringBuilder sb;
			list = new ArrayList<Integer>();
			list.add(numbers[n]);
			set.add(numbers[n]);
			for (int m = n+1; m < numbers.length; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}
			for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}	
		}
		System.out.println(getFormattedOutput(set));
	}
	private static String getFormattedOutput(Set<Integer> set){
		String finalNumbers = "";
		List<Integer> list = new ArrayList<Integer>();
		list.addAll(set);
		Collections.sort(list);
		List<String> finalList = new ArrayList<String>();
		for (Integer num : list) {
			String st = num.toString();
			if(st.length() == 1 ){
				finalList.add("{"+num+"}");
			}else{
				String st1 = "{";
				for (int i = 0; i < st.length(); i++) {
					if(st.length() -1 == i){
						st1 = st1+st.charAt(i);
					}else{
						st1 = st1+st.charAt(i)+" ";
					}
				}
				finalList.add(st1+"}");
			}
		}
		finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
		return finalNumbers;
	}

}

public class NumberCombinations {
	public static void main(String[] args) {
		int[] numbers = {1, 1, 2, 3};
		Set<Integer> set = new HashSet<Integer>();
		List<Integer> list = null;
		for (int n = 0; n < numbers.length; n++) {
			StringBuilder sb;
			list = new ArrayList<Integer>();
			list.add(numbers[n]);
			set.add(numbers[n]);
			for (int m = n+1; m < numbers.length; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}
			for (int m = 0; m < numbers.length-1 && n == numbers.length-1; m++) {
				sb = new StringBuilder();
				list.add(numbers[m]);
				Collections.sort(list);
				for (Integer num : list) {sb.append(num);}
				set.add(Integer.parseInt(sb.toString()));
			}	
		}
		System.out.println(getFormattedOutput(set));
	}
	private static String getFormattedOutput(Set<Integer> set){
		String finalNumbers = "";
		List<Integer> list = new ArrayList<Integer>();
		list.addAll(set);
		Collections.sort(list);
		List<String> finalList = new ArrayList<String>();
		for (Integer num : list) {
			String st = num.toString();
			if(st.length() == 1 ){
				finalList.add("{"+num+"}");
			}else{
				String st1 = "{";
				for (int i = 0; i < st.length(); i++) {
					if(st.length() -1 == i){
						st1 = st1+st.charAt(i);
					}else{
						st1 = st1+st.charAt(i)+" ";
					}
				}
				finalList.add(st1+"}");
			}
		}
		finalNumbers = finalList.toString().substring(1, finalList.toString().length()-1);
		return finalNumbers;
	}

}