# Shopping Options Amazon Online Assessment Test

Page Contents

## Shopping Options Amazon Online Assessment

Alternative Question: Find All Combination of Numbers Sum to Target

Given a positive integer, `target`, print all possible combinations of positive integers that sum up to the `target` number.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

For example, if we are given input ‘5’, these are the possible sum combinations.

``1, 42, 31, 1, 31, 2, 21, 1, 1, 21, 1, 1, 1, 1``

The output will be in the form a list of lists or an array of arrays. Each element in the list will be another list containing a possible sum combination.

• Recursion
• Two lists

## Solution

Program C++

```void print(vector<vector<int>> output){
for(int i = 0; i < output.size(); i++){
cout << "[ ";
for(int j = 0; j < output[i].size(); j++){
cout << output[i][j] << ", ";
}
cout << "]" << endl;
}
}

void print_all_sum_rec(
int target,
int current_sum,
int start, vector<vector<int>>& output,
vector<int>& result) {

if (target == current_sum) {
output.push_back(result);
}

for (int i = start; i < target; ++i) {
int temp_sum = current_sum + i;
if (temp_sum <= target) {
result.push_back(i);
print_all_sum_rec(target, temp_sum, i, output, result);
result.pop_back();

} else {
return;
}
}
}

vector<vector<int>> print_all_sum(int target) {
vector<vector<int>> output;
vector<int> result;
print_all_sum_rec(target, 0, 1, output, result);
return output;
}

int main(int argc, const char* argv[]) {
int n = 4;
vector<vector<int>> result = print_all_sum(n);

print (result);
}```

Program Java

```class sumCombinations{
static void print(ArrayList<ArrayList<Integer>> arr) {
for (int i = 0; i < arr.size(); i++) {
System.out.print("[");
for (int j = 0; j < arr.get(i).size(); j++) {
System.out.print(arr.get(i).get(j) + ", ");
}
System.out.println("]");
}
}

static void print_all_sum_rec(
int target,
int current_sum,
int start, ArrayList<ArrayList<Integer>> output,
ArrayList<Integer> result) {

if (target == current_sum) {
}

for (int i = start; i < target; ++i) {
int temp_sum = current_sum + i;
if (temp_sum <= target) {

print_all_sum_rec(target, temp_sum, i, output, result);
result.remove(result.size() - 1);
} else {
return;
}
}
}
static ArrayList<ArrayList<Integer>> print_all_sum(int target) {
ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> result = new ArrayList<Integer>();
print_all_sum_rec(target, 0, 1, output, result);
return output;
}
public static void main(String[] args) {
int n = 4;
ArrayList<ArrayList<Integer>> result = print_all_sum(n);
print (result);
}
}  ```

Program Python

```import copy

def print_all_sum_rec(target, current_sum, start, output, result):
if current_sum == target:
output.append(copy.copy(result))

for i in range(start, target):
temp_sum = current_sum + i
if temp_sum <= target:
result.append(i)
print_all_sum_rec(target, temp_sum, i, output, result)
result.pop()
else:
return

def print_all_sum(target):
output = []
result = []
print_all_sum_rec(target, 0, 1, output, result)
return output

n = 4
res = print_all_sum(n)
print(res)```

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution