Shopping Options Amazon Online Assessment Test

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.

See Also : Amazon Online Assessment Questions 2021 Preparation

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

1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 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.

Hint

  • 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) {
    output.add((ArrayList)result.clone());
  }

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

      result.add(i);
      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

Amazon Online Assessment Test Questions:

Leave a Comment