Facebook Interview Question
Software Engineer / DevelopersCountry: United States
After going through all the comments I hv found that people are not understading the question properly. Actually if a number has more than or equal to 2 occurrences then we also have to print the subset in which element has occurred more then 1 time..take a example if string is
112113 then we need to print all unique subset which are
111
112
113
123
So for doing this we store the numbers with their corresponding count(no. of occurence) for this I hv used map, we can use array also. And then we take the first element and decrease its count if now its count is 0 then it can't appear more than once so we increament the iterator and then we go for the subset of size two...
Once go through the below program u will be able to understand it easily..
#include<iostream>
#include<map>
using namespace std;
int main()
{
string s;
cout<<"enter the string "<<endl;
cin>>s;
map<char,int> mymap;
for(int i=0;i<s.length();i++)
{
if(mymap.find(s[i])==mymap.end())mymap[s[i]]=1;
else mymap[s[i]]++;
}
char arr[4];
arr[3]='\0';
map<char,int>::iterator it1,it2,it3;
for(it1=mymap.begin();it1!=mymap.end();it1++)
{
arr[0]=it1->first;
(it1->second)--;
it2=it1;
if(it1->second==0)it2++;
for(;it2!=mymap.end();it2++)
{
//if(it2->second >0)
arr[1]=it2->first;
it3=it2;
if(it2->second==1)it3++;
for(;it3!=mymap.end();it3++)
{
arr[2]=it3->first;
cout<<arr<<endl;
}
}
}}
Assuming the elements are unique, you can do nested for loops to ensure less than the normal 2^n runtime seen when generating all possible subsets.
public ArrayList<ArrayList<Integer>> set3(int [] nums) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
for (int i=0; i < nums.length - 2; i++) {
for (int j=i+1; j < nums.length -1; j++) {
for (int k=j+1; k < nums.length; k++) {
ArrayList<Integer> s = new ArrayList<Integer>();
s.add(nums[i]);
s.add(nums[j]);
s.add(nums[k]);
ret.add(s);
}
}
}
return ret;
}
@Anonymous yes the complexity of above codes is O(n^3), and its considered as better than O(2^n)..
I think we can't do it in better complexity than O(n^3)..
People, please understand, this is not power set because there is a fixed cordinality. This is why it should not be 2^n and the answer I believe is correct.
Can anyone show this not actually working?
Instead of a List<List<Integer>>, would this work for non-unique numbers by switching to a Set<Set<Integer>> ?
What about this simple solution? The assumption I made are:
- the input is a sorted array without duplication
- the result will contain sets shorter than 3 elements
- it's trivial to meet two above assumptions
void makeUniqueSubsets(vector<vector<int> > & result, vector<int> input)
{
for(int i = 0; i < input.size(); i++)
{
vector<int> newVector(1, input[i]);
int size = result.size();
for(int j = 0; j < size; j++)
{
if(result[j].size() < 3)
{
vector<int> copyVector = result[j];
copyVector.push_back(input[i]);
result.push_back(copyVector);
}
}
result.push_back(newVector);
}
}
Step 1: Sort the array. Time: O(n.lgn).
Step 2: Create another array (in same sorted order) but eliminating all repetitions. Time: Theta(n). Memory: O(n).
Step 3: Create pairs and store in a 2D array. Say the first element is at index 'k' in the given array. This will be paired with all elements from 'k+1' to 'n' in the given aray and stored at an appropriate index in 2D array. Do this for k=1 to n. Time: O(n^2). Memory: O(n^2). Note that all pairs are in themselves sorted and the 2D array will have all possible combinations of pairs.
Step 4: Extend the same logic to create all 3-member subsets. Use the larger number's index (element at (x,1) in 2D array) to create all three-member subsets ( If the larger value is at index k in the given array, use from indices 'k+1' to 'n' to create triplets). Time: O(n^3), Memory: O(n^3). Note: All triplets will be sorted and would exhaust all possible combinations out of the given set of size n.
The same can be extended to any number of desired elements in subsets, in polynomial time.
Why waste time in sorting and finding unique elements in the array? Find all triplets in time O(n^3) and for each triplet find sum of elements and sum of square of elements and keep storing it. For a new triplet, if sum and sum of square matches any stored triplet, then do the comparison of triplets otherwise it's unique till that point.
import java.io.*;
class SetTest
{
public static void main(String args[])
{
Console con=System.console();
int sum=0;
int no=Integer.parseInt(con.readline("enter how many nos"));
int arr[]=new int[no];
int brr[]=new int[no];
for(int i=0;i<arr.length;i++)
{
arr[i]=Integer.parseInt(con.readLine());
sum^=arr[i];
}
for(int i=0;i<brr.length;i++)
{
brr[i]=Integer.parseInt(con.readLine());
sum^=brr[i];
}
if(sum==0)
System.out.println("all the nos same");
else
System.out.println("all the nos are not same");
}
}
Sort the array, then count up how many times each item occurs and create another array in which the items occur only once. Then recurse through the arrays, building the sets.
import java.util.HashSet;
import java.util.Set;
public class createAllNCombos
{
static int count = 0;
public static void main (String [] args)
{
{
char [] chars = {'a','b','c'};
int charCounts [] = {3,2,2};
Set <String> perms = genPermutations(chars, charCounts, 3, 0, "");
for(String perm : perms)
{
System.out.println(perm);
}
System.out.println("PermutationsCount: " + count);
}
{
count = 0;
char [] chars = {'a','b','c', 'd', 'e'};
int charCounts [] = {1,1,1,1,1};
Set <String> perms = genPermutations(chars, charCounts, 3, 0, "");
for(String perm : perms)
{
System.out.println(perm);
}
System.out.println("PermutationsCount: " + count);
}
}
public static Set <String> genPermutations(char [] chars, int [] charCounts, int n, int at, String strSoFar)
{
count++;
Set <String> strings = new HashSet();
if(strSoFar.length() == n)
{
strings.add(strSoFar);
return strings;
}
else if(at < chars.length)
{
String tSoFar = "";
if(chars.length - at >= n - strSoFar.length())
strings.addAll(genPermutations(chars, charCounts, n, at+1, strSoFar));
for(int i = 0; i < charCounts[at]; i++)
{
tSoFar += chars[at];
if(i + strSoFar.length() >= n)
break;
strings.addAll(genPermutations(chars, charCounts, n, at+1, strSoFar + tSoFar));
}
}
return strings;
}
}
1. sort array in O(nlogn)
2. remove duplicate elements in one go O(n)
curr=1; i=1; // ignoring first element, which is not repetition
while(i<n)
{
if(arr[i]!=a[i-1])
{
if(curr!=i)
arr[curr]=arr[i];
curr++;
i++;
}
else
i++;
}
3. now curr is the length of final array, which has no repetition
using this we print final subsets
for(i=0 ; i<curr-2 ; i++)
for(j=i+1 ; j<curr-1 ; j++)
for(k=j+1 ; j<curr ; k++)
printf("[%d,%d,%d]\n",arr[i].arr[j],arr[k]);
This problem belongs to 3-SUM hard class of problem. It can be solved in O(n^2)
typedef struct triplet
{
int a;
int b;
int c;
}tr;
vector<tr> computeTriplet(vector<int> &list)
{
vector<tr> trList;
if(list.size() < 3) return trList;
int i, j, k;
sort(list.begin(), list.end());
for(i = 2; i < list.size(); i++)
{
j = 0;
k = i-1;
while(j < k)
{
int h = list[j] * list[j] + list[k] * list[k];
if (h > list[i] * list[i]) k--;
else if (h < list[i] * list[i]) j++;
else { trList.push_back((tr) {list[j], list[k], list[i]}); break;}
}
}
return trList;
}
After eliminating dublicate values, the code below will work.
List<List<Integer>> myList = new ArrayList<List<Integer>>();
for (int i = 0; i < array.length; ++i) {
for (int j = i + 1; j+1 < array.length; ++j) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(array[i]);
temp.add(array[j]);
temp.add(array[j+1]);
myList.add(temp);
}
}
for (int i=0; i<myList.size(); ++i) {
List<Integer> tmp = myList.get(i);
System.out.print(tmp.get(0));
System.out.print(",");
System.out.print(tmp.get(1));
System.out.print(",");
System.out.print(tmp.get(2));
System.out.print("\n");
}
Algorithm is as follows:
1) Go from i = 0 to i = n-2 of given array
2) For every i, get "hash" of elements A[i],A[i+1],A[i+2].
Hash is generated this way: elements A[i],A[i+1],A[i+2] are sorted and glued together with some separator. So. for {1,2,3} and {3,2,1} and {2,1,3} "hash" will be the same - "1|2|3".
3) Remember "hash" and its position in hash table: HashPositions["1|2|3"].push(i);
4) At the end, go through all HashPositions, and those which have only 1 position, are unique subsets.
Complexity:
1) We loop from 0 to n-2 (n-2 steps)
2) On every step we sort 3 elements (it takes constant time C)
3) At the end, we go through all hashes (maximum n-2 hashes)
So, complexity is C*(n-2) + (n-2) = (C+1)(n-2) = O(n)
Speedup: if we have sorted three elements A[i],A[i+1] and A[i+2] and need to get sorted next three elements A[i+1],A[i+2],A[i+3] we should not sort them again. We should just remove A[i] and insert A[i+3] into previous sorted array. It works faster.
public class ThreeMemberSubSet implements Serializable, Comparable<ThreeMemberSubSet> {
private static final long serialVersionUID = 1L;
private int firstValue ;
private int secondValue ;
private int thirdValue ;
/**
*
*/
public ThreeMemberSubSet() {
}
/**
* @param firstValue
* @param secondValue
* @param thirdValue
*/
public ThreeMemberSubSet(int firstValue, int secondValue, int thirdValue) {
super();
this.firstValue = firstValue;
this.secondValue = secondValue;
this.thirdValue = thirdValue;
}
/**
* @return the firstValue
*/
public int getFirstValue() {
return firstValue;
}
/**
* @param firstValue the firstValue to set
*/
public void setFirstValue(int firstValue) {
this.firstValue = firstValue;
}
/**
* @return the secondValue
*/
public int getSecondValue() {
return secondValue;
}
/**
* @param secondValue the secondValue to set
*/
public void setSecondValue(int secondValue) {
this.secondValue = secondValue;
}
/**
* @return the thirdValue
*/
public int getThirdValue() {
return thirdValue;
}
/**
* @param thirdValue the thirdValue to set
*/
public void setThirdValue(int thirdValue) {
this.thirdValue = thirdValue;
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
return this.toString().hashCode();
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
if ( obj == null ){
return false;
}
if (!(obj instanceof ThreeMemberSubSet)){
return false;
}
ThreeMemberSubSet otherObj = (ThreeMemberSubSet) obj;
if ( this.toString().equals(otherObj.toString())){
return true;
}
return false;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
StringBuilder toStringMsg = new StringBuilder();
toStringMsg.append("ThreeMemberSubSet::[");
toStringMsg.append(getFirstValue());
toStringMsg.append(getSecondValue());
toStringMsg.append(getThirdValue());
toStringMsg.append("]");
return toStringMsg.toString();
}
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(ThreeMemberSubSet otherObj) {
if (otherObj == null){
return 0;
}
if ( (this.getFirstValue() == otherObj.getFirstValue())
&& (this.getSecondValue() == otherObj.getSecondValue())
&& (this.getThirdValue() == otherObj.getThirdValue())) {
return 0;
}
if ( (this.getFirstValue() == otherObj.getSecondValue())
&& (this.getSecondValue() == otherObj.getFirstValue())
&& (this.getThirdValue() == otherObj.getThirdValue())) {
return 0;
}
if ( (this.getFirstValue() == otherObj.getThirdValue())
&& (this.getSecondValue() == otherObj.getFirstValue())
&& (this.getThirdValue() == otherObj.getSecondValue())) {
return 0;
}
if ( (this.getFirstValue() == otherObj.getFirstValue())
&& (this.getSecondValue() == otherObj.getThirdValue())
&& (this.getThirdValue() == otherObj.getSecondValue())) {
return 0;
}
if ( (this.getFirstValue() == otherObj.getSecondValue())
&& (this.getSecondValue() == otherObj.getThirdValue())
&& (this.getThirdValue() == otherObj.getFirstValue())) {
return 0;
}
if ( (this.getFirstValue() == otherObj.getThirdValue())
&& (this.getSecondValue() == otherObj.getSecondValue())
&& (this.getThirdValue() == otherObj.getFirstValue())) {
return 0;
}
return 1;
}
}
public class ThreeMemberSubSetEx {
public static void main(String[] args) {
SortedSet<ThreeMemberSubSet> uniqueSubset= new TreeSet<ThreeMemberSubSet>(constructThreeMemberSubset());
System.out.println( "Unique Value = " + uniqueSubset);
}
private static List<ThreeMemberSubSet> constructThreeMemberSubset(){
List<ThreeMemberSubSet> subset= new ArrayList<ThreeMemberSubSet>();
ThreeMemberSubSet ob1 = new ThreeMemberSubSet(1,2,3);
ThreeMemberSubSet ob2 = new ThreeMemberSubSet(2,1,3);
ThreeMemberSubSet ob3 = new ThreeMemberSubSet(1,3,2);
ThreeMemberSubSet ob4 = new ThreeMemberSubSet(2,3,1);
ThreeMemberSubSet ob5 = new ThreeMemberSubSet(3,2,1);
ThreeMemberSubSet ob6 = new ThreeMemberSubSet(3,1,2);
subset.add(ob1);
subset.add(ob2);
subset.add(ob3);
subset.add(ob4);
subset.add(ob5);
subset.add(ob6);
return subset;
}
}
Better logic:
A 3 element subset (3e) can be one of following form:
(a,b,c) (3 different numbers)
(a,a,b)
(a,a,a)
Now loop through the array and eliminate repeated number, mark number of appearance for them as (1, 2 or >3) ---> S1, S2, S3
List out all (a,b) which a is from S2 and b is from S1 or S2
List out all (a,b,c) which all from S1 and a<b<c
So, from that observation, you can see that we only need to separate number which appear only 1 time in the array and others which appear more than 1 in the array.
That is my idea, and the complexity can be minimal as N^3
Perl implementation:
#input: abcdefg 3
#Note: the string should be sorted and all letters should be distinct
# This program can output any length of non-duplicate
# combinations given a string and a length n
#!/usr/bin/perl
$str = <stdin>;
chomp($str);
($s, $n) = split(' ', $str);
$st = substr $str, 0, $n;
$ary{$st} = 1;
#print $st."|".$n."\n";
subset($n, $s);
for my $key (keys %ary){
$count ++;
print $key." ".$count."\n";
}
sub subset{
$index = $_[0];
$str = $_[1];
if($index >= length($str)){ # Stop at the string end
return;
}
#print $index."\t".$str."\t".$st."\n";
$st = substr $str, $index, 1;
#print $index."\t".$str."\t".$st."\n";
my %hash = ();
for my $key (keys %ary){ # Go through each previous combination
for($i = 0; $i < $n; $i ++){
my $k = $key;
substr($k, $i, 1) = ''; # Remove one element
$k = $k.$st; # Add a new one
#print $key." ".$k." ".$i." ".$n." ".$st."\n";
if($hash{$k} != 1){ # Check if this has been generated
$hash{$k} = 1;
}
}
}
@ary{keys %hash} = values %hash; # union the two hashes into one
subset($index + 1, $str); #Repeat this until the end of the string
}
This can be done recursively for K out of N numbers.
Assuming unique numbers here is c++ code.
// Print C(N,K) numbers in order of N^K, but not 2^N.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void PrintNcK(vector<int> &arN, int K);
void _PrintNcK(vector<int> &arN, vector<int> &arK, int cur, int start, int end);
void PrintNcK(vector<int> &arN, int K)
{
vector<int> arK;
arK.assign(K,1);
_PrintNcK(arN, arK, 0, 0, arN.size()-K+1);
}
void _PrintNcK(vector<int> &arN, vector<int> &arK, int cur, int start, int end)
{
if(cur == arK.size()) {
// Print the combination
for(int i=0;i<arK.size();i++)
cout << arK[i] << " ";
cout << endl;
return;
}
for(int i=start; i<end;i++) {
arK[cur] = arN[i];
_PrintNcK(arN, arK, cur+1, i+1, end+1); // Recurse here
}
}
int main()
{
vector<int> arN;
arN.push_back(15);
arN.push_back(5);
arN.push_back(12);
arN.push_back(6);
arN.push_back(2);
arN.push_back(4);
arN.push_back(41);
arN.push_back(49);
arN.push_back(20);
sort(arN.begin(), arN.end(), greater<int>());
int N = arN.size(), K = 3;
PrintNcK(arN,K);
return 0;
}
int[] arr = {0,2,3,3,2,0};
arr = ArrayUtils.removeDuplicates(arr);
int n = arr.length;
int k = 3;
List<List<Integer>> subsets = generateSubsets(arr, 0, 3);
public List<List<Integer>> generateSubsets( final int[] arr, int index, int size){
if( size > (arr.length-index) ){
return new ArrayList<>();
}
if( size == 1 ){
List<List<Integer>> oneElementSubsets = new ArrayList<>();
for( int i = index; i < arr.length; i++ ){
oneElementSubsets.add( create(arr[i]) );
}
return oneElementSubsets;
}
List<List<Integer>> allSubsets = new ArrayList<>();
List<List<Integer>> smallerSizeSubsets = generateSubsets(arr, index+1, size-1);
for( List<Integer> curSubset : smallerSizeSubsets ){
List<Integer> singleElem = create(arr[index]);
singleElem.addAll( curSubset );
allSubsets.add( singleElem );
}
List<List<Integer>> sameSizeSubsets = generateSubsets(arr, index+1, size);
for( List<Integer> curSubset : sameSizeSubsets ){
allSubsets.add( curSubset );
}
return allSubsets;
}
**
*
* Given an array, find all unique three-member subsets,
* with unique being that [0,2,3] and [3,2,0] are the same set.
* Should run in faster than 2^n time
* @author patrick
*
*/
public class UniqueGroup {
public static void main(String[] args) {
int[] values = new int[] {1, 2, 3, 4, 5};
List<int[]> r = unique(values);
for(int[] t : r) {
System.out.println("[" + t[0] + " " + t[1] + " " + t[2] + "]");
}
}
public static List<int[]> unique(int[] values) {
List<int[]> results = new ArrayList<int[]>();
for(int j=0; j<values.length; j++) {
int a = values[j];
int i=j;
int k=j+1;
while(i< values.length-2) {
results.add(new int[] {a, values[i+1], values[k+1]});
k++;
if(k==values.length-1) {
i++;
k=i+1;
}
}
}
return results;
}
}
package com.my.tst;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class SetOfThree {
public Set<String> getGroupsOfThree(int[] in){
Set<String> groupSet = new HashSet<String>();
Stack<Integer> group = new Stack<Integer>();
doGetGroupsOfThree(in, 0, group, groupSet);
return groupSet;
}
public void doGetGroupsOfThree(int[] in, int start, Stack<Integer> group, Set<String> groupSet){
if(group.size() == 3){
addGroup(group, groupSet);
return;
}
if(start >= in.length || group.size() + in.length - start < 3){
return;
}
for(int i = start; i<in.length; i++){
group.push(in[i]);
doGetGroupsOfThree(in,i+1,group, groupSet);
group.pop();
}
}
void addGroup(Stack<Integer> group, Set<String> groupSet){
Integer[] intArray = group.toArray(new Integer[group.size()]);
Arrays.sort(intArray);
String groupString = Arrays.asList(intArray).toString();
if(!groupSet.contains(groupString)){
groupSet.add(groupString);
System.out.println(groupString);
}
}
}
package com.my.tst;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class SetOfThree {
public Set<String> getGroupsOfThree(int[] in){
Set<String> groupSet = new HashSet<String>();
Stack<Integer> group = new Stack<Integer>();
doGetGroupsOfThree(in, 0, group, groupSet);
return groupSet;
}
public void doGetGroupsOfThree(int[] in, int start, Stack<Integer> group, Set<String> groupSet){
if(group.size() == 3){
addGroup(group, groupSet);
return;
}
if(start >= in.length || group.size() + in.length - start < 3){
return;
}
for(int i = start; i<in.length; i++){
group.push(in[i]);
doGetGroupsOfThree(in,i+1,group, groupSet);
group.pop();
}
}
void addGroup(Stack<Integer> group, Set<String> groupSet){
Integer[] intArray = group.toArray(new Integer[group.size()]);
Arrays.sort(intArray);
String groupString = Arrays.asList(intArray).toString();
if(!groupSet.contains(groupString)){
groupSet.add(groupString);
System.out.println(groupString);
}
}
}
This is a basic solution in python. Sort out the elements, get a unique array and then iterate. Since we are looking for sets repetitions are not allowed ({1,1,3} is not a valid solution)
def subsets(array):
if(len(array) < 3):
raise Exception("There must be at least 3 elements")
sortedArray = sorted(array) #n log n
uniques = [sortedArray[0]]
item = sortedArray[0]
for s in sortedArray:
if(s!=item):
item = s
uniques.append(item)
for i in range(len(uniques)-2):
for j in range(i+1,len(uniques)-1):
for k in range(j+1,len(uniques)):
print str(uniques[i]) + ' ' + str(uniques[j]) + ' ' + str(uniques[k])
Another simple solution with time o(n^2).
void PrintUniqueTriplets(int[] arr)
{
int n = arr.Length;
Hashtable h = new Hashtable();
string s = "";
int min,max,mid;
for (int i = 0; i < n ; i++)
{
for (int j = 0; j < n - 1; j++)
{
min = Math.Min(arr[i], Math.Min(arr[j], arr[j + 1]));
max = Math.Max(arr[i], Math.Max(arr[j], arr[j + 1]));
mid = arr[i] + arr[j] + arr[j + 1] - min - max;
s = min.ToString() + mid.ToString() + max.ToString();
if (i == j || i==j+1 || h.ContainsKey(s))
continue;
h.Add(s, 1);
Console.WriteLine(arr[i] + " " + arr[j] + " " + arr[j + 1]);
}
}
}
Another solution with Time O(n^2).
void PrintUniqueTriplets(int[] arr)
{
int n = arr.Length;
Hashtable h = new Hashtable();
string s = "";
int min,max,mid;
for (int i = 0; i < n ; i++)
{
for (int j = 0; j < n - 1; j++)
{
min = Math.Min(arr[i], Math.Min(arr[j], arr[j + 1]));
max = Math.Max(arr[i], Math.Max(arr[j], arr[j + 1]));
mid = arr[i] + arr[j] + arr[j + 1] - min - max;
s = min.ToString() + mid.ToString() + max.ToString();
if (i == j || i==j+1 || h.ContainsKey(s))
continue;
h.Add(s, 1);
Console.WriteLine(arr[i] + " " + arr[j] + " " + arr[j + 1]);
}
}
}
void PrintUniqueTriplets(int[] arr)
{
int n = arr.Length;
Hashtable h = new Hashtable();
string s = "";
int min,max,mid;
for (int i = 0; i < n ; i++)
{
for (int j = 0; j < n - 1; j++)
{
min = Math.Min(arr[i], Math.Min(arr[j], arr[j + 1]));
max = Math.Max(arr[i], Math.Max(arr[j], arr[j + 1]));
mid = arr[i] + arr[j] + arr[j + 1] - min - max;
s = min.ToString() + mid.ToString() + max.ToString();
if (i == j || i==j+1 || h.ContainsKey(s))
continue;
h.Add(s, 1);
Console.WriteLine(arr[i] + " " + arr[j] + " " + arr[j + 1]);
}
}
}
static void PrintUniqueTriplets(int[] arr)
{
int n = arr.Length;
Hashtable h = new Hashtable();
string s = "";
int min,max,mid;
for (int i = 0; i < n ; i++)
{
for (int j = 0; j < n - 1; j++)
{
min = Math.Min(arr[i], Math.Min(arr[j], arr[j + 1]));
max = Math.Max(arr[i], Math.Max(arr[j], arr[j + 1]));
mid = arr[i] + arr[j] + arr[j + 1] - min - max;
s = min.ToString() + mid.ToString() + max.ToString();
if (i == j || i==j+1 || h.ContainsKey(s))
continue;
h.Add(s, 1);
Console.WriteLine(arr[i] + " " + arr[j] + " " + arr[j + 1]);
}
}
}
/*
Given an array, find all unique three-member subsets, with unique being that [0,2,3] and [3,2,0] are the same set. Should run in faster than 2^n time
*/
#include <iostream>
#include <vector>
using namespace std;
/* Main Code Starts from here */
void solve(vector< vector<int> > &vii, vector<int> &res, vector<int> &vi, int pos, int n) {
if(n==3) {
vii.push_back(res);
return;
}
else {
for(int i=pos; i<vi.size(); ++i) {
res.push_back(vi[i]);
solve(vii, res, vi, i+1, n+1 );
res.pop_back();
}
}
}
vector<vector <int> > subset(vector<int> vi) {
vector< vector<int> > vii;
vector<int> subvec;
solve(vii, subvec, vi,0, 0);
return vii;
}
int main() {
int arr[] = {1,2,3,4,5};
vector<int> vi(arr, arr+sizeof(arr)/sizeof(int) );
vector< vector<int> > out = subset(vi);
for(auto i: out) {
for(auto j: i)
cout << j << " ";
cout<< endl;
}
return 0;
}
void print3SubSets(int[] arr, int ai, int[] sol, int level, bool marked[][] marked) {
if(level == 4) {
print(sol, level);
}
if(ai >= arr.length()) {
return;
}
if(marked[level][arr[i]] == false) {
marked[level]arr[i]] = true;
sol[level] = arr[i];
print3SubSets(arr, ai + 1, sol, level +1 , marked);
for(int i = level + 1; i <= 3; i++) {
for(int j = 0; j < 9; j++) {
marked[i][j] = false;
}
}
print3SubSets(arr, ai + 1, sol, level +1 , marked);
} else {
print3SubSets(arr, ai + 1, sol, level, marked);
}
}
This code will be ok.
void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & v, std::vector<int> & cnt,
std::vector<int> & path, int k, int t) {
if (path.size() == t) {
rs.push_back(path);
} else {
for (int i = k; i < v.size(); i++) {
if (cnt[i] > 0) {
cnt[i]--;
path.push_back(v[i]);
Trace(rs, v, cnt, path, i, t);
path.pop_back();
cnt[i]++;
}
}
}
}
std::vector<std::vector<int> > KSubset(std::vector<int> & num, int k) {
std::map<int, int> tmap;
for (int i = 0; i < num.size(); i++) {
if (!tmap.count(num[i])) tmap[num[i]] = 0;
tmap[num[i]]++;
}
std::vector<int> v;
std::vector<int> cnt;
for (std::map<int, int>::iterator i = tmap.begin(); i != tmap.end(); i++) {
v.push_back(i->first);
cnt.push_back(i->second);
}
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, v, cnt, path, 0, k);
return rs;
}
void findSubsets(int[] input)
{
List<List<Integer>> map=new ArrayList<List<Integer>>();
HashSet<Integer> hs=new HashSet<Integer>();
List<List<Integer>> mapOutput=new ArrayList<List<Integer>>();
for(int i=0;i < input.length;i++)
{
int mapsize=map.size();
for(int j=0;j < mapsize;j++)
{
if(((hs.contains(input[i]) && map.get(j).contains(input[i])) || !hs.contains(input[i])) && map.get(j).size()< 3)
{
ArrayList<Integer> temp=new ArrayList<Integer>(map.get(j));
temp.add(input[i]);
map.add(temp);
if(temp.size()==3)
mapOutput.add(temp);
}
}
ArrayList<Integer> singleElement=new ArrayList<Integer>();
singleElement.add(input[i]);
map.add(singleElement);
hs.add(input[i]);
}
System.out.println(mapOutput);
}
public ArrayList<ArrayList<Integer>> kMemberSubsetsWithDup(int[] a, int k){
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//ArrayList<Integer> empty = new ArrayList<Integer>();
//list.add(empty);
if(a == null || a.length < k){
return list;
}
Arrays.sort(a);
subsets(list, a, new ArrayList<Integer>(), 0, k);
return list;
}
public void subsets(ArrayList<ArrayList<Integer>> list, int[] a,
ArrayList<Integer> cur, int start, int k){
if(cur.size() == k){
list.add(cur);
}
for(int i = start; i < a.length; i++){
cur.add(a[i]);
subsets(list, a, new ArrayList<Integer>(cur), i+1, k);
cur.remove(cur.size() - 1);
while(i + 1 < a.length && a[i] == a[i+1]){
i++;
}
}
}
public ArrayList<ArrayList<Integer>> kMemberSubsetsWithDup(int[] a, int k){
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//ArrayList<Integer> empty = new ArrayList<Integer>();
//list.add(empty);
if(a == null || a.length < k){
return list;
}
Arrays.sort(a);
subsets(list, a, new ArrayList<Integer>(), 0, k);
return list;
}
public void subsets(ArrayList<ArrayList<Integer>> list, int[] a,
ArrayList<Integer> cur, int start, int k){
if(cur.size() == k){
list.add(cur);
//should return here
return;
}
for(int i = start; i < a.length; i++){
cur.add(a[i]);
subsets(list, a, new ArrayList<Integer>(cur), i+1, k);
cur.remove(cur.size() - 1);
while(i + 1 < a.length && a[i] == a[i+1]){
i++;
}
}
}
- Alex April 21, 2013