There can be recursive way which is more or less the brute force way. Just a small piece of code here:
PS: path dis an array which will keep your element in the subset, idx is the index for this path array. Try visualizing it by drawing the recursive tree.
void subset(int n, int idx, int path, int a, int start)
// this implies this we have considered all elements.
print the path array here
// either dont consider the array element a[start]
// so here, just do the recursive call
subset(n,idx,path,a,start+1); // notice the change in the function call. Only start gets incremented. The idx and path array remains same
path[idx]=a[start]; // i.e. we consider the element a[start] in the subset
Another approach is there using bits which is well explained here. Also, one more way of printing all the subsets which is however, of the same complexity. But its generally used in printing all k-size subsets of the given set. We basically use bitmasking. The main idea is we find the lowest n-bit number with k-bits set. lets say, we want to find subsets of size 2 of the array whose size is say 5
(1,2,3,4,5), of the given array. Then, my lowest n-bit number with 2 bits set is: 00011. Every i’th bit set as 1 denotes inclusion of a[i] element and 0 denotes ignoring the same element. Thus this number represents the set: (4,5). We’ll now find the next higher number with same bits set which is 00101 which represents the set (3,5). Find next higher and repeat till the maximum value you can have. Using this code also, we can find all subsets. See here.
This may be an inefficient approach, but lets say, I have an undirected graph which has n nodes and n*n edges i.e. every node connecting other, n is the length of my array. Then all permutation are just all my dfs traversals of this graph. However there exists a solution using backtracking i.e.I am fixing an element at the first position, recursive for n-1. The pseudocode goes like:
void permutation(int n, int a, int path, int idx, int start)
// base case, all elements have been considered.
print the path array here
// now at this position idx lets say we had one element but we can have any element from a[start...n]
// interchange the element at path[idx] and a[start]
// do the recursive call
// revert the change made above
This is explained here with a recursion tree. Using
STL, you can do the same easily with an add-on. The function next_permutation will generate the next permutation of the given string.
Taking as a string:
And you used
permutations/combinations. Did you mean they are same? I seriously don’t think so. Permutations refers to:
all possible arrangements of the given array
and combinations are :
the way of selecting members from a group such that the order of selection doesn't matter. This suggests that, if we are given an array of size n, then we can select all subsets(explained above) of the array i.e. select a set of 1(nC1) element or 2 elements(nC2) and so on..
Hope it clears…