Amazon Interview Question SDE-3s
Country: India
Below is the code that works for any set of elements.
If we should somehow use the knowledge that the elements are 1,2,..,9, maybe, we should pre-compute all of possible results and store them in "n,k" => sets hashmap.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<vector<int>> SumSets(vector<int> const &a, int n, int16_t k,
unordered_map<uint64_t, vector<vector<int>>> &memo, int16_t idx = 0)
{
vector<vector<int>> out;
if (k < 0 ||
n < 0 ||
idx < 0)
{
return out;
}
if (k == 0 &&
n == 0)
{
out.resize(1);
return out;
}
if (idx > a.size()) {
return out;
}
uint64_t memo_key = (static_cast<uint64_t>(k) << 48) | (static_cast<uint64_t>(idx) << 32) | n;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
out = SumSets(a, n - a[idx], k - 1, memo, idx + 1);
for (auto &s : out) {
s.push_back(a[idx]);
}
auto skip = SumSets(a, n, k, memo, idx + 1);
out.insert(out.end(), skip.begin(), skip.end());
memo[memo_key] = out;
return memo[memo_key];
}
int main()
{
unordered_map<uint64_t, vector<vector<int>>> memo;
auto out = SumSets({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 3, memo);
for (auto &s : out) {
for (int n : s) {
cout << n << ", ";
}
cout << "\n";
}
}
import copy
def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers = copy.copy(numbers)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k-n, new_set, result)
k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)
for r in result:
print(r)
import copy
def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers = copy.copy(numbers)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k-n, new_set, result)
k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)
for r in result:
print(r)
import copy
def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers = copy.copy(numbers)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k-n, new_set, result)
k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)
for r in result:
print(r)
// Practicas.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int k = 3;
int n = 18;
int d[] = {1,2,3,4,5,6,7,8,9};
int *indx = new int[k];
for(int i=0; i<k; i++)
indx[i]=i;
int ci=k-1;
while(indx[0] < 9 - k)
{
while(indx[ci] < 9)
{
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
indx[ci]++;
}
for(int i=k-1; i>0; i--)
{
if(indx[i] == 9)
{
indx[i - 1] ++;
for(int j=i; j< k;j++)
indx[j] = indx[j - 1] + 1;
}
}
}
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
return 0;
}
// Practicas.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int k = 3;
int n = 18;
int d[] = {1,2,3,4,5,6,7,8,9};
int *indx = new int[k];
for(int i=0; i<k; i++)
indx[i]=i;
int ci=k-1;
while(indx[0] < 9 - k)
{
while(indx[ci] < 9)
{
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
indx[ci]++;
}
for(int i=k-1; i>0; i--)
{
if(indx[i] == 9)
{
indx[i - 1] ++;
for(int j=i; j< k;j++)
indx[j] = indx[j - 1] + 1;
}
}
}
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
return 0;
}
public static List<List<Integer>> findKElementsSum(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 1: i < n - 2; i++ ) {
for (int J = i + 1: j < n - 1; j++ ) {
int r = n - (i + j);
if (r != i && r != j && r <= n && r > 0) {
list.add(Arrays.asList(i, j, r));
}
}
}
return list;
}
private Set<Set<Integer>> findkElementsSum(int[] list, int n, int k) {
return combinations(list, k).stream().filter(sumIs(n)).collect(toSet());
}
private Set<Set<Integer>> combinations(int[] list, int k) {
Set<Set<Integer>> finalAnswer = Arrays.stream(list).mapToObj((IntFunction<HashSet<Integer>>) HashSet::new).collect(toSet());
for (int i = 0; i < k; i++) {
Set<Set<Integer>> result = new HashSet<>();
for (Set<Integer> lowerCombination : finalAnswer) {
for (int element : list) {
HashSet<Integer> biggerCombination = new HashSet<>(lowerCombination);
if (!biggerCombination.contains(element)) {
biggerCombination.add(element);
result.add(biggerCombination);
}
}
}
finalAnswer = result;
}
return finalAnswer;
}
private Predicate<Set<Integer>> sumIs(int n) {
return integers -> sum(integers) == n;
}
private Integer sum(Set<Integer> integers) {
return integers.stream().reduce(0, (a, b) -> a + b);
}
private Set<Set<Integer>> findkElementsSum(int[] list, int n, int k) {
return combinations(list, k).stream().filter(sumIs(n)).collect(toSet());
}
private Set<Set<Integer>> combinations(int[] list, int k) {
Set<Set<Integer>> finalAnswer = Arrays.stream(list).mapToObj((IntFunction<HashSet<Integer>>) HashSet::new).collect(toSet());
for (int i = 0; i < k; i++) {
Set<Set<Integer>> result = new HashSet<>();
for (Set<Integer> lowerCombination : finalAnswer) {
for (int element : list) {
HashSet<Integer> biggerCombination = new HashSet<>(lowerCombination);
if (!biggerCombination.contains(element)) {
biggerCombination.add(element);
result.add(biggerCombination);
}
}
}
finalAnswer = result;
}
return finalAnswer;
}
private Predicate<Set<Integer>> sumIs(int n) {
return integers -> sum(integers) == n;
}
private Integer sum(Set<Integer> integers) {
return integers.stream().reduce(0, (a, b) -> a + b);
}
import copy
def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)
new_numbers = copy.copy(numbers)
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)
k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)
for r in result:
print(r)
import copy
def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)
new_numbers = copy.copy(numbers)
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)
k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)
for r in result:
print(r)
import copy
def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)
new_numbers = copy.copy(numbers)
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)
k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)
for r in result:
print(r)
import copy
def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)
new_numbers = copy.copy(numbers)
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)
new_numbers.remove(n)
get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)
k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)
for r in result:
print(r)
subset sum problem is NP complete. There is a pseudo polinomial algorithm ala knapsack to solve it for small sums - which has limitted value in parctice.
- Chris December 10, 2017