A9 Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Complexity isn't really O(2^N). Rather, it's (N choose k), which comes down to O(n!/k!(n-k)!).Depending on what K is, it can be anywhere between O(n) to O(n!).
@Killedsteel when we generate a subset, each element has the “possibility” of either being in there or not. That is, for the first element, there are 2 choices. For the second, there are two, etc. So, doing 2 * 2 * ... * 2 n times gives us 2^n subsets. We will not be able to do better than this in time or space complexity.
Imagine that we would like to print all subsets. Then each integer from array 'int a[]' is member of the subset or not. This can be solved recursively by passing two additional arguments 'int lo' and 'String accum'. Given the index 'lo' we either add a[lo] to an accumulation string or not, increment 'lo' and perform recursive call. We stop and print the 'accum' string as soon as 'lo' is equal to the length of 'a'.
Now, given problem is essentially the same except one modification of the base case. We print the string if and only if its length is equal to 'k', the length of the subset.
A sample code is shown below:
public static void print(int K, int N) {
int[] a = new int[N];
for (int k=0; k<N; k++) a[k] = k+1;
print(a, K, 0, "");
}
private static void print(int[] a, int K, int lo, String s) {
if (s.length() == K) System.out.println("'" + s + "'");
if (s.length() >= K) return;
if (a.length == lo) return;
print(a, K, lo+1, s);
print(a, K, lo+1, s+a[lo]);
}
Recursive Solution.
Time Complexity: O(2 ^ n)
package GraphSearch;
import java.util.ArrayList;
import java.util.List;
class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}
private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
result.add(new ArrayList<Integer>(subset));
return;
}
for(int i = pos; i < nums.length; i++){
subset.add(nums[i]);
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}
public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}
package GraphSearch;
import java.util.ArrayList;
import java.util.List;
class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}
private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
result.add(new ArrayList<Integer>(subset));
return;
}
for(int i = pos; i < nums.length; i++){
subset.add(nums[i]);
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}
public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}
package GraphSearch;
import java.util.ArrayList;
import java.util.List;
class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}
private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
result.add(new ArrayList<Integer>(subset));
return;
}
for(int i = pos; i < nums.length; i++){
subset.add(nums[i]);
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}
public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}
void print(const vector<int> &a)
{
for (int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;
}
void dfs(int i, int cnt, int n, vector<int> &a)
{
if (cnt == 0)
{
print(a); return;
}
if (n - i + 1 < cnt) return;
a.push_back(i); dfs(i + 1, cnt - 1, n, a); a.pop_back();
dfs(i + 1, cnt, n, a);
}
void printKSetOfN(int n, int k)
{
assert(n > 0 && k > 0 && k <= n);
vector<int> a;
dfs(1, k, n, a);
}
what do you think of this solution ?
public static void printSubset(int k,int n) {
printSubsetRec(n,k,1,1,new int[k]);
}
private static void printSubsetRec(int n,int k,int i,int level, int[] out) {
if(level>k) {
for(int o:out) {
System.out.print(o+",");
}
System.out.print("\n");
return;
}
for(int L=i;L<=n-k+level;L++) {
out[level-1]=L;
printSubsetRec(n,k,L+1,level+1,out);
}
}
public static void printSubset(int k,int n) {
printSubsetRec(n,k,1,1,new int[k]);
}
private static void printSubsetRec(int n,int k,int i,int level, int[] out) {
if(level>k) {
for(int o:out) {
System.out.print(o+",");
}
System.out.print("\n");
return;
}
for(int L=i;L<=n-k+level;L++) {
out[level-1]=L;
printSubsetRec(n,k,L+1,level+1,out);
}
}
Recursive printout of k-combination of numbers 1 to n
void printComb(int start, int end, int k, vector<int>& line)
{
if(k == 0)
{
for(int j = 0; j < line.size(); j++)
cout << line[j] << " ";
cout << endl;
}
else
{
for(int i = start; i <= end; i++)
{
line.push_back(i);
printComb(i+1, end, k-1, line);
line.pop_back();
}
}
}
public class SubsetOfSizeKOutOfN {
public static void main(String[] args) {
SubsetOfSizeKOutOfN so = new SubsetOfSizeKOutOfN();
System.out.println(so.solution(4, 2));
}
public List<List<Integer>> solution(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
int[] num = new int[n];
for (int i = 0; i < num.length; i++) {
num[i] = i + 1;
}
int numOfSubset = 1 << n;
for (int i = 0; i < numOfSubset; i++) {
if (isSizeK(i, k, n)) {
List<Integer> s = getSubset(num, i, n);
ans.add(s);
}
}
return ans;
}
private List<Integer> getSubset(int[] num, int mask, int n) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
subset.add(num[i]);
}
}
return subset;
}
private boolean isSizeK(int mask, int k, int n) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
++cnt;
}
}
return cnt == k;
}
}
1. generate int array A based on sample range from 1 ... N
2. generate all subsets of A of size K.
3. print results
complexity: O(2^n)
implementation:
public static void main(String[] args) { int n = 4; int k = 2; int a[] = getArrayFromN(n); List<List<Integer>> lists = generateSubsetsSizeM(a, k); for (List<Integer> arrayList : lists) { printList(arrayList); System.out.println(); } } private static int[] getArrayFromN(int n) { int j = 0; int a[] = new int[n]; for(int i = 1; i <= n; i++) { a[j] = i; j++; } return a; } public static List<List<Integer>> generateSubsetsSizeM(int a[], int size) { List<List<Integer>> result = new ArrayList<>(); int max = new Double(Math.pow(2, a.length)).intValue(); int k = 0, index = 0; for(int i = 0; i < max; i++) { k = i; index = 0; List<Integer> list = new ArrayList<>(); while(k > 0) { if ((k & 1) > 0) { list.add(a[index]); } k = k >> 1; index++; } if (list.size() == size) { result.add(list); } } return result; }// output for N = 4 and K = 2:
- guilhebl April 27, 20151 2
1 3
2 3
1 4
2 4
3 4