## Google Interview Question for Software Developers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

I found one of the following solutions online. Can anyone explain this in a really simple way? A diagram would also help in visualizing stack and recursion.

``````import java.util.Stack;

public class GetAllSubsetByStack {

/** Set a value for target sum */
public static final int TARGET_SUM = 15;

private Stack<Integer> stack = new Stack<Integer>();

/** Store the sum of current elements stored in stack */
private int sumInStack = 0;

public void populateSubset(int[] data, int fromIndex, int endIndex) {

/*
* Check if sum of elements stored in Stack is equal to the expected
* target sum.
*
* If so, call print method to print the candidate satisfied result.
*/
if (sumInStack == TARGET_SUM) {
print(stack);
}

for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

if (sumInStack + data[currentIndex] <= TARGET_SUM) {
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];

/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
sumInStack -= (Integer) stack.pop();
}
}
}

/**
* Print satisfied result. i.e. 15 = 4+6+5
*/

private void print(Stack<Integer> stack) {
StringBuilder sb = new StringBuilder();
sb.append(TARGET_SUM).append(" = ");
for (Integer i : stack) {
sb.append(i).append("+");
}
System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
}
}

public class Main {

private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
14, 15 };

public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

@milincjoshi :
You do not need to do recursion at all, to solve this sort of problem. Observe that the problem can be partitioned into two unrelated problems.

[1] Given a list of list, find which lists has the exact sum as S.
Now, if you were to think in terms of SQL, that will be :

``select from whatever where sum( all columns ) == S``

Which is a very neat and easy problem to solve.

[2]
Now, who generates this list of list? That is where the problem lies. The problem says, all possible subsets of a set. Ah. That is a power set. Google it up. There are many ways to generate a list of all possible subsets of a set, and one is clearly through recursion.

But that is the lamest way of doing it, computationally. Here, we can use Ramanujan's method. What is that?
Imagine for every item in the set ( list ) you can choose to take the item, and choose not to take the item. So, if the list is :

{ 1, 3, 4, 5, 6, 15 }.

You can say, for 1, 0 ( not select ) , for 3 : 0, ... for 15 0.
That would be : 00000 --> 0.
That selects the subset, empty set.
In the same way :
00001 --> 1. selects the subset { 15 }.

So, what did we learn? We learn that iterating over different binary representation of
0 to 2^n where n is the number of items in the list, we can generate a pattern
which can then be used to select the corresponding subset!

That concludes our problem [2]!

Now, anyone can easily solve the problem with much cleaner, and neater code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> SumSets(vector<int> const &a, int sum,
unordered_map<uint64_t, vector<vector<int>>> &memo, int idx = 0)
{
vector<vector<int>> sets;
if (sum == 0) {
sets.push_back(vector<int>());
return sets;
}
if (sum < 0 ||
idx >= a.size())
{
return sets;
}
uint64_t memo_key = ((uint64_t)idx << 32) | sum;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}

vector<vector<int>> subsets = SumSets(a, sum - a[idx], memo, idx + 1);
for (auto const & subset : subsets) {
vector<int> set{a[idx]};
set.insert(set.end(), subset.begin(), subset.end());
sets.push_back(set);
}

subsets = SumSets(a, sum, memo, idx + 1);
sets.insert(sets.end(), subsets.begin(), subsets.end());

memo[memo_key] = sets;
return memo[memo_key];
}

int main()
{
vector<int> a = {1, 3, 4, 5, 6, 15};
unordered_map<uint64_t, vector<vector<int>>> memo;
vector<vector<int>> sets = SumSets(a, 15, memo);
for (auto const &set : sets) {
for (int n : set) {
cout << n << ", ";
}
cout << "\n";
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I recursively create subgroups of the initial int array and sum their values.
* If the value is greater than the target value - we keep on recursing
* If the value is less than the target value, we stop the current recursion branch
* In order to avoid duplicates, we keep a set of all the visited subgroups (we do this by creating a unique string key out of the current int array and keep track of it in a hash table)

* This code can be coded without recursion (use queue instead)
* One thing that can be done better here: instead of using a string, use some kind of function to generate unique ID per int array

I have come up with the following code

``````#include "CommonHeader.h"

static std::unordered_set<std::string> V;
static std::string makeKeyFromVector(const std::vector<int>& numbers)
{
std::string k;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { k += std::to_string(n); });
return k;
}

static void findSubgroupsForTargetInternal(
const std::vector<int>& numbers, int target, std::vector<std::vector<int> >& result)
{
// If we already visited this branch, skip it
std::string k = makeKeyFromVector(numbers);
if(V.count(k)) return;
V.insert(k);

int sum = 0;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { sum += n; });
if(sum == target) {
// An exact match - add it to the result vector and return
result.push_back(numbers);
return;
} else if(sum < target) {
// No need to continue
return;
}

// The result is gt than the target, try removing one element and try again
std::vector<int> nextSetOfNumbers = numbers;
for(size_t i = 0; i < nextSetOfNumbers.size(); ++i) {
int numberToRemove = nextSetOfNumbers[i];
nextSetOfNumbers.erase(nextSetOfNumbers.begin() + i);
findSubgroupsForTargetInternal(nextSetOfNumbers, target, result);
nextSetOfNumbers.insert(nextSetOfNumbers.begin() + i, numberToRemove);
}
}

std::vector<std::vector<int> > findSubgroupsForTarget(const std::vector<int>& numbers, int target)
{
std::vector<std::vector<int> > result;
findSubgroupsForTargetInternal(numbers, target, result);
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe that this is the fastest solution using "binary" counter to get all subsets. No recursion is needed, no duplicates

``````#include "CommonHeader.h"

typedef std::vector<int> IntVec_t;

#define CHECK_BIT(var, pos) (var & (1 << pos))
std::vector<IntVec_t> findSubsets(const IntVec_t& numbers, int target)
{
// Number of subsets is 2^N where N is the number of elements (including empty set)
// we look at the problem as binary counter, for example:
// { 1, 3, 4, 5, 6, 15 }
//   0  0  0  0  0  1  (1 dec) {15}
//   0  0  0  0  1  0  (2 dec) {6}
//   0  0  0  0  1  1  (3 dec) {6, 15}
// ...
std::vector<IntVec_t> result;
int noSets = pow(2, numbers.size());
for(int i = 0; i < noSets; ++i) {
int sum = 0;
IntVec_t subset;
for(size_t j = 0; j < numbers.size(); ++j) {
if(CHECK_BIT(i, j)) {
sum += numbers[j];
subset.push_back(numbers[j]);
}
}
if(sum == target) {
result.push_back(subset);
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

First shot : Recursion
N=15 , Ai >0
Iteration through array and assume that a given element is part of our candidate subset, whose value is Ai.
F(N) = {Ai} + F(N-Ai) if N > Ai
Declare as answer if N = Ai
Abandon a subset N < Ai ,

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Iterator;
import java.util.Stack;

public class TargetSum {
public static int TARGET_SUM = 15;
public static int[] INPUT = {1, 3, 4, 5, 6, 15};

public void findSubsetWithTargetSum(Stack<Integer> stack, int startIndex, int sum) {
if (sum == 0) {
printSubset(stack);
} else if (startIndex < INPUT.length) {
// Select INPUT[startIndex] and find subset from startIndex+1 with target sum-INPUT[startIndex]
int selected = INPUT[startIndex];
if (sum >= selected) {
stack.push(selected);
findSubsetWithTargetSum(stack, startIndex + 1, sum - selected);
stack.pop();
}
// Find subset from startIndex+1 with target sum
findSubsetWithTargetSum(stack, startIndex + 1, sum);
}
}

public void printSubset(Stack<Integer> stack) {
Iterator<Integer> iter = stack.iterator();
System.out.print("Subset found: { ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println("}");
}

public static void main(String[] args) {
TargetSum sum = new TargetSum();
Stack<Integer> stack = new Stack<Integer>();

sum.findSubsetWithTargetSum(stack, 0, TARGET_SUM);
}
}

// OUTPUT:
// Subset found: { 1 3 5 6 }
// Subset found: { 4 5 6 }
// Subset found: { 15 }``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Iterator;
import java.util.Stack;

public class TargetSum {
public static int TARGET_SUM = 15;
public static int[] INPUT = {1, 3, 4, 5, 6, 15};

public void findSubsetWithTargetSum(Stack<Integer> stack, int startIndex, int sum) {
if (sum == 0) {
printSubset(stack);
} else if (startIndex < INPUT.length) {
// Select INPUT[startIndex] and find subset from startIndex+1 with target sum-INPUT[startIndex]
int selected = INPUT[startIndex];
if (sum >= selected) {
stack.push(selected);
findSubsetWithTargetSum(stack, startIndex + 1, sum - selected);
stack.pop();
}
// Find subset from startIndex+1 with target sum
findSubsetWithTargetSum(stack, startIndex + 1, sum);
}
}

public void printSubset(Stack<Integer> stack) {
Iterator<Integer> iter = stack.iterator();
System.out.print("Subset found: { ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println("}");
}

public static void main(String[] args) {
TargetSum sum = new TargetSum();
Stack<Integer> stack = new Stack<Integer>();

sum.findSubsetWithTargetSum(stack, 0, TARGET_SUM);
}
}

// Output:
// Subset found: { 1 3 5 6 }
// Subset found: { 4 5 6 }
// Subset found: { 15 }``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@NoOne. That's correct. If we'd like to solve this by generating all subsets and checking if each subset has the needed sum, it's easy to do by using a bit set. But it's a brute force, and time complexity is O(N * 2 ^ N). A top down solution (not necessary recursive) with memoization, has time complexity O(N * S), where S is the needed sum, if we treat S as not a constant. If we have a limit for S, then, time is only O(N), which is a big difference with O(N * 2 ^ N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Solution.
We assume the given target sum is positive and the given array is sorted.

def gen_list(ts, current_array, current_list=[]):
if ts == 0:
print(current_list)
results.append(current_list)
return
elif len(current_array) == 0:
return
for i in range(1, ts+1):
if i in current_array:
if len(current_list) == 0 or i >= current_array[0]:
gen_list(ts-i, [x for x in current_array if x >= i][1:], current_list + [i])

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python solution given the target sum is positive and the given array is sorted.

``````def gen_list(ts, current_array, current_list=[]):
if ts == 0:
print(current_list)
results.append(current_list)
return
elif len(current_array) == 0:
return
for i in range(1, ts+1):
if i in current_array:
if len(current_list) == 0 or i >= current_array[0]:
gen_list(ts-i, [x for x in current_array if x >= i][1:], current_list + [i])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the non-recursive version, based on NoOne's hint, time complexity: O(2^N)

``````vector<vector<int>> all_subset_sums_bf(const vector<int>& nums, int target)
{
// try all combinations in an efficient "binary counting way"
int sum = 0; // current sum
vector<int> nums_set = remove_dublicates(nums);
vector<vector<int>> results;
vector<bool> big_int(nums_set.size(), false); // specialized vector, is a bit vector
while (true) {
// do manual increment:
// - if I set a bit to 1, I add the nums_set[bit-idx] to the sum
// - if I clear a bit, I subtract the nums_set[bit-idx] from the sum
size_t idx;
for (idx = 0; idx < big_int.size(); idx++) {
if (big_int[idx]) {
sum -= nums_set[idx];
big_int[idx] = false;
} else {
big_int[idx] = true;
sum += nums_set[idx];
break;
}
}
if (idx >= big_int.size()) break; // all combinations tried
if (sum == target) {
results.push_back({});
for (idx = 0; idx < big_int.size(); idx++) {
if (big_int[idx]) {
results.back().push_back(nums_set[idx]);
}
}
}
}
return results;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the iterative, pseudo polynomial time algorithm (like knap-sack) which has expensive costs, when many results are generated in the backtracking step.

``````// reduced problem, only positive nums, positive target,
vector<vector<int>> all_subset_sums_dp(const vector<int>& nums, int target)
{
// go through all nums and check in how many ways target can be built
auto nums_set = remove_dublicates(nums);
vector<vector<bool>> dp(nums_set.size() + 1, vector<bool>(target + 1));
dp[0][0] = true; // base case
for (size_t i = 0; i < nums_set.size(); ++i) {
int num = nums_set[i];
dp[i + 1] = dp[i];
for (int s = num; s <= target; ++s) {
if (dp[i][s - num]) { // can extend using num
dp[i + 1][s] = true;
}
}
}

// backtrack to reconstruct the solutions
stack<StackItem> stack;
vector<vector<int>> results;
if(dp.back().back()) { // wa there at least one solution
stack.push({ {}, target, dp.size() - 1 });
}
while (!stack.empty()) {
if (stack.top().rem_sum > 0) { // can stop here, no need to backtrack 'till -1
stack.top().dp_idx--;
size_t dp_idx = stack.top().dp_idx;
int rem_sum = stack.top().rem_sum;
if (rem_sum >= nums[dp_idx] && dp[dp_idx][rem_sum - nums[dp_idx]]) { // sum has been achieved with
if (dp[dp_idx][rem_sum]) { // sum has as well been achieved without
stack.push({ stack.top() }); // clone
}
stack.top().rem_sum -= nums[dp_idx];
stack.top().set.push_back(nums[dp_idx]);
}
} else {
results.push_back(move(stack.top().set));
stack.pop();
}
}
return results;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

and maybe the interesting part, a simple run-time comparison of the different algorithms (memo, is basically Alex's version)

``````---------------------------------------
numbers: {1, 3, 4, 5, 6, 15}
target: 15

algo brute force ran in 1.419 ms
algo dp (memo) ran in 5.286 ms
algo dp (p.poly) ran in 2.706 ms
---------------------------------------
numbers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
target: 50

algo brute force ran in 353.478 ms
algo dp (memo) ran in 149.093 ms
algo dp (p.poly) ran in 15.262 ms
---------------------------------------
numbers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
target: 25

algo brute force ran in 4505.34 ms
algo dp (memo) ran in 36.832 ms
algo dp (p.poly) ran in 12.317 ms
---------------------------------------
numbers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}
target: 465

skip brute force, takes too long
algo dp (memo) ran in 244.602 ms
algo dp (p.poly) ran in 85.866 ms
---------------------------------------
numbers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}
target: 444

skip brute force, takes too long
algo dp (memo) ran in 257.729 ms
algo dp (p.poly) ran in 95.207 ms
---------------------------------------
numbers: {1, 2, 10000, 20000, 30000}
target: 30003

algo brute force ran in 0.326 ms
algo dp (memo) ran in 1.561 ms
algo dp (p.poly) ran in 673.041 ms``````

as expected, brute force is quite slow in most cases, and the pseudo polynomial (ala knapsack) is not good on large values.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Thank you for the tests! :)
I think time complexity of my approach is O(N * S), because the memo key is constructed as a pair of idx and sum. So, the max number of memo entries is N * S. If a memo entry already exists, the recursion doesn't go deeper.
Just for my sanity purpose, I wrote a random test (generating random vectors and sum) to compare my algorithm with brute force. No diffs found.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Both recursion and DP

``````public static void main(String[] args) throws java.lang.Exception {
int[] arr = { 1, 3, 4, 5, 6, 15 };
int sum = 15;
getsubsets(arr, sum, 0, new ArrayList<Integer>());

countsubsets(arr, sum);
}

public static void getsubsets(int[] arr, int sum, int i, List<Integer> list) {
if (sum < 0)
return;
if (sum == 0) {
System.out.println(list);
return;
}
if (i < 0 || i > arr.length - 1)
return;

int n = arr.length;
for (int k = i; k < n; k++) {
getsubsets(arr, sum - arr[k], k + 1, list);
list.remove(new Integer(arr[k]));
}
}

public static void countsubsets(int[] arr, int sum){
int n = arr.length;
int[][] dp = new int[sum+1][n+1];

for(int i = 1; i <= sum; i++){
for(int j = 1; j <= n; j++){
if(i > arr[j-1])
dp[i][j] = dp[i-arr[j-1]][j-1];
else
dp[i][j] = dp[i][j-1];

if(arr[j-1] == i)
dp[i][j] += 1;
}
}
System.out.println("DP soln - ");
System.out.println("count - " + dp[sum][n]);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following C# implementation uses a custom class to holds the sum and its subset as a stack. (No recursion)

``````using System;
using System.Collections.Generic;

namespace PracticeTests
{
public class TargetSum
{
public int sum;
public Stack<int> subset; // Stack for each subset.
public TargetSum(int s, Stack<int> sub)
{
this.sum = s;
this.subset = sub;
}
}

public class SubSetToTarget
{
public SubSetToTarget()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }; //12.122ms
int sum = 50;
FindSubSets(arr, sum);
}

private void FindSubSets(int[] arr, int target)
{
int n = arr.Length;
List<TargetSum> subsets = new List<TargetSum>();
for (int i = 0; i < n; i++)
{
int curr = arr[i];
foreach (TargetSum ts in subsets)
{
if (ts.sum == curr)
{
ts.subset.Push(curr);
PrintSubSet(ts.subset);
}

if ((ts.sum - curr) > curr)
{
ts.subset.Push(curr);
ts.sum -= curr;
}
else
{
int prev = ts.subset.Pop();
ts.sum = ts.sum - (curr - prev);
ts.subset.Push(curr);
}
}

//Add a new element to the list
TargetSum newTS = new TargetSum(target - curr, new Stack<int>());
newTS.subset.Push(curr);

//Handling the edge case where current element is the target
if (newTS.sum == 0)
PrintSubSet(newTS.subset);
}
}

private void PrintSubSet(Stack<int> set)
{
Console.Write("{ ");
foreach (Object obj in list)
Console.Write(obj + ", ");
Console.Write("}");
Console.WriteLine();
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex, it's not O(N * target): assuming S is your target in your O(N*S) runtime observation.
- sequence {1,2,3,..,30}: N=30
- target = 10: n*target = 300, number of returned subsets: 10
- target = 20: n*target = 600, number of returned subsets: 64
- target = 50: n*target = 1500, number of returned subsets: 3351
- target = 100: n*target = 3000, number of returned subsets: 198732
(results are actually the same from your and mine code)
you can't create more subsets with at least one element than your upper bound.
As I mentioned, you can count in O(N*S) or you can decide if any subset sums to target in O(N*S) but you can't create all subsets in that time, because this number seem to grow faster than N*S.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. That's correct. It's worse than O(N * S). My mistake is that I counted the recursion tree nodes (there are really N * S nodes), but didn't take in account that each node doesn't do a constant time calculations. Each node iterates over multiple subsets.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution works for a sorted array with positive numbers and positive target sum

1. For each number, either include that number or exclude it.
2. If you include the number, recursively call the function for the remaining array, target sum being original_target_sum - current_number
3. If you exclude the number, recursively call the function for the remaining array, target sum being original_target_sum
4. If at any point the target_sum is the same as the current number, that means the sum for that branch of the recusrive tree is equal to the target sum. Print the numbers in that branch.
5. If the target_sum is less than the current number, then there is no point in going forward with that branch, as the sum will always be greater than the target sum.
6. Return if current is equal to length, meaning we've reached the end of the target array.

``````def findSubsets(targetArray, current, length, targetSum, resultArray):
if targetSum == targetArray[current]:
resultArray.append(targetArray[current])
print resultArray
elif targetSum < targetArray[current]:
return
elif current >= length:
return
else:
newResultArray = resultArray[:] #pass array by reference
findSubsets(targetArray, current + 1, length, targetSum, newResultArray)
resultArray.append(targetArray[current])
newResultArray = resultArray[:]
findSubsets(targetArray, current + 1, length, targetSum - targetArray[current], newResultArray)

def main():
targetArray = [1, 3, 4, 5, 6, 15]
findSubsets(targetArray, 0, len(targetArray), 15, [])

if __name__ == '__main__':
main()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def printOption( option ):
output = "[ "
for item in option:
output += "{0},".format( str(item) )
print output.rstrip( ',' ) + " ]"

def getSumSets( input, sum, option ):
for int in input:
option.append( int )

if sum - int == 0:
printOption( option )

elif sum - int > 0:
getSumSets( input[input.index(int)+1:], sum - int, option )

option.pop()

if __name__ == "__main__":
input = [ 1, 3, 4, 5, 6, 15 ]
getSumSets( input, 15, [] )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//C++98
#include <vector>
#include <iostream>
using namespace std;

vector<int> subtract(vector<int> list, vector<int> temp){
vector<int> res = vector<int>();
for(int i = 0; i < list.size(); i++){
if(find(temp.begin(), temp.end(), list[i]) == temp.end())
res.push_back(list[i]);
}
return res;
}

vector<int> copy(vector<int> subset){
vector<int> dup = vector<int>();
for(int i = 0; i < subset.size(); i++)
dup.push_back(subset[i]);
return dup;
}

void concat(vector<vector<int> >& subsets, vector<vector<int> > extension){
for(int i = 0; i < extension.size(); i++)
subsets.push_back(copy(extension[i]));
}

void duplicate(vector<vector<int> >& subsets, int& index){
index = subsets.size();
if(index == 0)
return;
vector<vector<int> > original = vector<vector<int> >();
concat(original, subsets);
concat(subsets, original);
}

void findAllSubsets(vector<int> list, vector<vector<int> >& result, int& index){
if(list.size() == 0)
return;
if(result.empty()){
vector<int> subset = vector<int>();
result.push_back(subset);
}
duplicate(result, index);
for(int i = index; i < result.size(); i++){
result[i].push_back(list[0]);
}
list.erase(list.begin());
findAllSubsets(list, result, index);
}

void display(vector<vector<int> > subsets){
cout << "{";
for(int i = 0; i < subsets.size(); i++){
cout << "{";
for(int j = 0; j < subsets[i].size(); j++)
(j < subsets[i].size() - 1) ? cout << subsets[i][j] << ", " : cout << subsets[i][j];
cout << "}";
}
cout << "}" << endl;
}

vector<vector<int> > filter(vector<vector<int> > subsets, int target){
vector<vector<int> > result = vector<vector<int> >();
for(int i = 0; i < subsets.size(); i++){
int sum = 0;
for(int j = 0; j < subsets[i].size(); j++)
sum += subsets[i][j];
if(sum - target == 0)
result.push_back(subsets[i]);
}
return result;
}

int main(){
vector<int> list = vector<int>();
list.push_back(1);
list.push_back(3);
list.push_back(4);
list.push_back(5);
list.push_back(6);
list.push_back(15);
int target = 15;
vector<vector<int> > result = vector<vector<int> >();
int index = 0;
findAllSubsets(list, result, index);
result = filter(result, target);
display(result);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// C++98
// Recursive top-down: Starting from the target number and subtracting numbers in the array from the target to find a set with 0 residual
#include <vector>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

void display(vector<int> list){
for(int i = 0; i < list.size(); i++)
(i < list.size() - 1) ? cout << list[i] << ", " : cout << list[i] << endl;
}

vector<int> subtract(vector<int> list, vector<int> subset){
vector<int> sub = vector<int>();
for(int i  = 0; i < list.size(); i++){
if(find(subset.begin(), subset.end(), list[i]) == subset.end())
sub.push_back(list[i]);
}
return sub;
}

void copy(vector<int>& source, vector<int> temp){
for(int i = 0; i < temp.size(); i++){
source.push_back(temp[i]);
}
}

bool findSubset(vector<int> list, int target, vector<int>& subset){
if(target == 0)
return true;
if(list.empty())
return false;
for(int i = 0; i < list.size(); i++){
vector<int> temp = vector<int>();
copy(temp, subset);
temp.push_back(list[i]);
if(findSubset(subtract(subtract(list, subset), temp), target - list[i], temp)){
subset.clear();
copy(subset, temp);
return true;
}
}
}

string toString(vector<int> subset){
stringstream signature;
for(int i = 0; i < subset.size(); i++)
(i < subset.size() - 1) ? signature << subset[i] << "-" : signature << subset[i];
return signature.str();
}

vector<vector<int> > findSubsets(vector<int> list, int target){
vector<vector<int> > subsets = vector<vector<int> >();
vector<string> map_ = vector<string>();
for(int i = 0; i < list.size(); i++){
vector<int> subset = vector<int>();
subset.push_back(list[i]);
vector<int> new_list = subtract(list, subset);
if(findSubset(new_list, target - list[i], subset)){
sort(subset.begin(), subset.end());
if(find(map_.begin(), map_.end(), toString(subset)) == map_.end()){
map_.push_back(toString(subset));
subsets.push_back(subset);
}
}
}
return subsets;
}

void display(vector<vector<int> > subsets){
cout << "{";
for(int i = 0; i < subsets.size(); i++){
cout << "{";
for(int j = 0; j < subsets[i].size(); j++)
(j < subsets[i].size() - 1) ? cout << subsets[i][j] << ", " : cout << subsets[i][j];
cout << "}";
}
cout << "}" << endl;
}

int main(){

vector<int> list = vector<int>();
list.push_back(1);
list.push_back(3);
list.push_back(4);
list.push_back(5);
list.push_back(6);
list.push_back(15);
int target = 15;

vector<vector<int> > subsets = findSubsets(list, target);
display(subsets);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy Peasy Japaneesey

``````void subSum(int[] arr, int N, int len, List<Integer> soFar)
{
List<Integer> newfar = new ArrayList<>(soFar);
for(int i=len-1;i>=0;i--)
{
if(arr[i] == N)
{
subSum(arr, N, i, newfar);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void subSum(int[] arr, int N, int len, List<Integer> soFar)
{
List<Integer> newfar = new ArrayList<>(soFar);
for(int i=len-1;i>=0;i--)
{
if(arr[i] == N)
{
subSum(arr, N, i, newfar);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void subSum(int[] arr, int N, int len, List<Integer> soFar)
{
List<Integer> newfar = new ArrayList<>(soFar);
for(int i=len-1;i>=0;i--)
{
if(arr[i] == N)
{
subSum(arr, N, i, newfar);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.