Writing Sum as Combinations and permutations from given array

Few days ago, I came across a question on quora which goes like this:

How do you solve this programming problem? Imagine you want to find all permutations of 2, 3, and 7 that can add up to make 10. (Ex: 2, 2, 2, 2, 2; or 3 , 7).

The question is basically asking us to represent sum using numbers from the array where a number can be used more than once.
Consider, the original example:

sum = 10
nums = [2, 3, 7]

We can use 2 five times to make sum 10. Also we consider 7 + 3 and 3 + 7 both as solution candidates.
At first glance, I thought the problem is related to subset sum. But no, we are allowed to use single number more than once and permutations is allowed. So, we’ll be using the recursion just like subset sum approach with slight modification i.e we are allowed to take same item again and again.

Solution:

The problem like this is easy to solve by recursion. Let’s try to visualize the solution recursively.
But, before that let’s talk about how would you solve it without code?
We have a list of numbers nums = [2, 3, 7] and we want to find all the combinations that make up the sum including the permutations.

eg: [3,7] and [7,3] to make 10

My approach would be like this:

1. Start with sum 10 and an empty list.
2. Include the first element 2 to the list. Solve for sum == 10 - 2 = 8 and [2].
3. Include the second element 3 to the list. Solve for sum == 10 - 3 = 7 and [3].
4. Include the third element 7 to the list. Solve for sum == 10 - 7 = 3 and [7].
5. Solve subproblems with sum = x and list ans recursively.

If it doesn’t make much sense don’t worry, here is the recursion tree recursion tree.

Here, we start with f(10, []) and at every states we take {2, 3, 7} and add to our answer list such that sum is greater than or equal to the number.
For every state f(sum, ans) we have 3 choices(if num is less than or equal to sum):

• Include 2 to the ans and solve for sum - 2
• Include 3 to the ans and solve for sum - 3
• Include 7 to the ans and solve for sum - 7

We can see at level 1, we have:

             — f(8, [2]) // Take 2
   f(10, []) — f(7, [3]) // Take 3
             — f(3, [7]) // Take 7

The nodes marked in gray in the recursion tree are the answers to the problem.
Here is the complete code in Python:

def solve(sum, ans):
    # If sum becoms 0 we have found the required list
    if sum == 0:
        print(ans)
    
    # Include every other element to make the sum
    # Number that is included also can be included
    for elem in nums:
        if sum - elem >= 0:
            solve(sum - elem, ans + [elem])
 
# We want to make the sum from list nums
nums = [2, 3, 7]
sum = 10
 
# Call solve with sum and an empty list 
solve(sum, [])

Output:

[2,  2,  2,  2,  2]
[2,  2,  3,  3]
[2,  3,  2,  3]
[2,  3,  3,  2]
[3,  2,  2,  3]
[3,  2,  3,  2]
[3,  3,  2,  2]
[3,  7]
[7,  3]

Read More

Leetcode 78: Subsets

In this post, I'm going to talk about a problem on leetcode which asks us to find all the possible subsets of given list of integers. This problem is the base to solving other problems like subset sum and subset partitioning which I'll be discussing in coming posts. Let's get started: I'll be solving this problem using 2 techniques:

1. Using Recursion
2. Using Bitset

I'll be using cpp for this task.
Problem Statement: Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example: Input:

nums = [1,2,3]

Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

1. Using Recursion

Firstly, I'll be discussing recursive approach to subset finding problem. Recursive problem is easy to visualise. Consider the given testcase [1, 2, 3]. Let solve(nums, n, subset) be the function that find subsets for array nums and number of elements n, initially called with an empty subset. So our initial call is :

vector<int>subset;
solve(nums, nums.size(), subset);

Now lets try visualising how recursion tree looks like.
Recursive Cases: For every state i.e (n), i,e position n - 1 of

solve(nums, n, subset)

we can have 2 choices:(Try to visualise recursion for arr = {1, 2, 3} )

• Don’t include the current element in the subset i.e simply call

solve(nums, n - 1, subset);

• Include current element in the subset
  

  subset.push_back(arr[n -  1]);
  solve(nums, n -  1, subset);
  

Base Cases:
Let’s think of base cases. The base cases are:

• If n == 0 i.e no item left push the current subset to our subsets_ which is a vector of vector.
  

  if (n == 0){
  subsets_.push_back(subset);
  return;
  }
  

  Complete Code:
  

  class Solution {
  public:
  // Vector of vector of int to store all the subsets
  vector<vector<int>> subsets_;
  
  // Solve method that generates subset recursively
  void solve(vector<int> &nums, int n, vector<int> subset){
      // If size of array becomes 0, no elemnts are left
      // We push current subset to our subsets_ and return
      if (n == 0){
          subsets_.push_back(subset);
          return;
      }
      // Else we have 2 options:
  
      // Don't include the current element to subset
      solve(nums, n - 1, subset);
      // Incldue the current element in subset
      subset.push_back(nums[n - 1]);
      solve(nums, n - 1, subset);
  }
  
  // Solution method subsets
  vector<vector<int>> subsets(vector<int>& nums) {
      // Make an empty vector subset
      vector<int> subset;
      // Call solve function initially with an empty subset 
      solve(nums, nums.size(), subset);
      // Return subsets after calculation
      return subsets_;
  }
  };
  

2. Using Bitset

I have explained the bitset method on quora.

Read More