Programming Interview 11: Print all subset of an array

Step by step to crack Programming Interview questions 11: Print all subset of an array

Solution:

Step 1: Decide how many elements in a sub-set:
---Possible number of subset: 0 to array length;

Step 2: Recursively process elements from left to right:
---A boolean array to keep track of what elements to print;
---An alternative can be using swapping ;
---A start-index to know the next start index to be processed;
---A value to represent the remaining elements to be processed.

Thank you for watching.

[nghiaho]

Nice clean code. You can optimize it further with:
    for(int i=start; i < nums.length - remain + 1; i++)
that avoids exploring subsets that will never get printed. I found it useful to add a global counter to see how often PrintSubset got called before/after the change.

[AI_Edu_]

You have two ways. First method is to define the list outside of the method, as a class-scope variable, so you can add a permutation to the list whenever you found. Second method is to add a list pointer as part of the parameter for the permutation method.

[ApoorvAgarwalContact]

the case at line no. 32 is possible many times for an instance when for subset of size =2 last call after (3, 4) call made (4, ..) would be passing i+1 = num.length in that case you will have that condition as true.

[digimeon]

I did this on c++:

void subsetsArr( vector<int> arr, vector<int> cons ){
if( arr.size() > 0 ){
int aux = arr[ arr.size() - 1 ];
arr.pop_back();

subsetsArr( arr, cons );

cons.push_back( aux );
for( int i = cons.size() - 1; i >= 0; i-- ){
cout << cons[i];
}
cout << endl;

subsetsArr( arr, cons );
}
}

[AI_Edu_]

Thanks I should have mentioned that I assumed there is no duplicate values. The problem to remove duplicates if there is any in all subsets is much more difficult than this subset problem (unless we are allowed to use powerful data structure like hashmap), and it's more difficult than a similar problem of print unique permutations for a string allowing duplicates. It's a good question to think about but I have no idea how to solve it. :(

[AI_Edu_]

I don't think my code breaks for the example. It should include. Did you get this by running my example sorry?

[titombo]

I just removed this statement and apparently it still gives me the right answer.
Strange, still didn't understand why it is in there. I am quite curious :P

[titombo]

One thing I didn't understand, if somebody could explain I really appreciate it.

why you check if (start+remain>nums.length). Didn't understand the comment in it:

//now is the key recursive part, we need process char by char from the start position until end before that, we need determine whether we proceed or not to check if start+remain>nums.length not possible even if all remaining element to be used

[MrEugeneleo]

I have a question, if I not just want to print, but also return a Arraylist of all permutations, is the solution similar, haimenboy?? Same questions as the power set problem.

[clarenceanne]

how to get rid of the ", " at the end?
ex: { 1, 2, 3, }

[legorabbit]

hmm...you should think about the duplicate elements in the array. it is "set".

[Gioeufshi]

what about bitmasks? :/

a very simple solution