Shopping Options Amazon OA 2022 Solution

Page Contents

Shopping Options Amazon OA Solution

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.

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
Shopping Options Amazon OA
Shopping Options Amazon OA

SOLUTION

Program: Shopping Options Amazon OA Solution in 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: Shopping Options Amazon OA Solution in 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: Shopping Options Amazon OA Solution in 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)

Related: Amazon OA Online Assessment 2021 Questions and Answers