Google Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
@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.
#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;
}
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;
}
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;
}
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 }
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 }
@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).
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])
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])
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;
}
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;
}
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.
@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.
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++) {
list.add(arr[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]);
}
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);
subsets.Add(newTS);
//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();
}
}
}
@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.
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()
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, [] )
//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;
}
// 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);
}
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);
newfar.add(arr[i]);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
newfar.add(arr[i]);
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}
}
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);
newfar.add(arr[i]);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
newfar.add(arr[i]);
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}
}
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);
newfar.add(arr[i]);
System.out.println(newfar);
return;
}
if(arr[i]<N)
{
newfar.add(arr[i]);
subSum(arr, N-arr[i], i, newfar);
newfar = new ArrayList<>(soFar);
}
}
}
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.
- milincjoshi September 28, 2017import 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); } }