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

What are *args and **kwargs in Python

In this post, I'm going to talk about *args and **kwargs in Python which is a useful concept while handling multiple arguments.

They are called *args and **kwargs in Python which allows the function to accept optional arguments(positional and keyword).
Let’s see with an example.
At first, let’s make a simple function that accepts a single argument, first_name.

>>> def person(first_name):
...     print(first_name)
>>> person("Ram")
Ram
>>> person()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: person() missing 1 required positional argument: 'first_name'

What we can see is first_name is a compulsory argument. So, it is not possible to call the function without arguments.
Now, what we are going to do is make a function that accepts first_name as compulsory arguments followed by last_name as an optional argument.
One way to do this would be

>>> def person(first_name, last_name=""):
...     print(first_name, last_name)
>>> person("Ram") # Called with 1 argument
Ram
>>> person("Ram", "Shrestha") # Called with 2 arguments
Ram Shrestha

So far everything is going well. But now we want to scale the same function to accept first_name(compulsory) and last_name and middle_name as positional arguments.
One simple trick is to add another argument middle_name.

>>> def person(first_name, last_name="", middle_name=""):
...     print(first_name, middle_name, last_name)

But there is a more concise way to scale the function to accept multiple optional arguments called *args in Python.

1. *args

*args collects extra positional arguments as a tuple

The idea is simple. We modify our function definition as:

>>> def person(first_name, *args):
...     print(first_name, end = " ")
...     for names in reversed(args):
...             print(names, end=" ")
...     print()
>>> # Accepts single argument
>>> person("Ram")
Ram
>>> # Accepts 2 arguments 
>>> person("Ram", "Chhetri")
Ram Chhetri
>>> # Accepts 3 arguments
>>> person("Ram", "Chhetri", "Lal")
Ram Lal Chhetri
>>> person("Ram", "Chhetri", "Lal", "Krishna")
Ram Krishna Lal Chhetri

We can see that now our function can accept first_name followed by last_name, middle_name as optional positional arguments. To see if args is indeed a tuple you can add

print(type(args))

inside of function definition
Let’s see another example:

Task 1: Write a function to add N integers which are passed as arguments ( N >= 1)
Let’s do it for 1 integer

>>> def add(a):
...     return a
>>> add(8)
8

Nothing complicated. Now do it for 2 integers

>>> def add(a, b):
...     return a + b
>>> add(8, 2)
10
>>> add(8)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: add() missing 1 required positional argument: 'b'

Notice?? We lost the compatibility for 1 argument.
This is where *args comes handy:

>>> def add(a, *args):
...     sum = a
...     print(type(args))
...     for num in args:
...         sum += num
...     return sum
>>> add(8)
8
>> add(8, 2)
10
>> add(8, 2, 5)
15

See how flexible it is using *args. Note it is not necessary to name *args as args . We can name it whatever we like. But it must be preceded with a *.

2. **kwargs

**kwargs collects extra positional arguments as a dictionary.

Let’s return to our previous examples of function person:

Task 2: Modify function person so that it accepts additional optional parameters phone_num, email and so on…as keywords.
We modify our original function definition to accept a new argument **kwargs which is a keyword argument as:

>>> def person(first_name, *args, **kwargs):
...     print(first_name, end=" ")
...     for names in reversed(args):
...             print(names, end=" ")
...     print()
...     # Since kwargs is a dictionary
...     # we can iterate using .items()
...     for key, value in kwargs.items():
...             print(key, value)
>>> person("Ram", "Chhetri", "Lal", phone_num="981128331", email="anon@testmail.com")

Ram Lal Chhetri
phone_num 981128331
email anon@testmail.com

Since kwargs is of dictionary type. we can iterate over key, value using .items()
Notes:

• *args and **kwargs are used to allow the function to accept a variable number of arguments
• *args collects positional arguments as a tuple whereas **kwargs as dictionary
• args and kwargs are just naming convention. You can name it whatever you like.
• * and ** are also used in value unpacking

Read More