🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:
Input: candidates = [2], target = 1
Output: []

Example 4:
Input: candidates = [1], target = 1
Output: [[1]]

Example 5:
Input: candidates = [1], target = 2
Output: [[1,1]]

Solution:

If you have already gone through few of other problems in the Unbounded Knapsack Problem series, it might have naturally occurred to you that this problem is very similar to Unbounded Knapsack Problem. You can think about this problem in the following way:

• Given a knapsack of maximum weight capacity T (which is same as target in the given problem in this chapter) and an array of items where items[i] has weight weights[i], compute the total number number of ways you can fill up the knapsack with the given items such that the weight of the knapsack becomes exactly equal to T. You can put as many instances (0 or more) of each items in the knapsack. weights[] is same as the array of distinct integers in the given problem.

So, we have been able to translate the given problem into a well known classic Dynamic Programming problem which is Unbounded Knapsack Problem in this case.

From my experience, whenever I have identified a problem to be similar to Unbounded Knapsack Problem I have found designing a space optimized bottom-up algorithm based on 1D array is much more intuitive than the bottom-up 2D array based algorithm. When designing a bottom-up DP algorithm based on 1D array for problems similar to Unbounded Knapsack Problem figuring out the base case(s) become really simpler than the 2D array based solutions. In 1D array based solution generally we only have to care about one base case that dp[0].

So adhering to the template discussed in Unbounded Knapsack Problem chapter we get the following algorithm:

• Suppose dp[w] gives the list of all unique combinations, where w = 0 to Target.
  If there exists one or more combination with sum equal to w then dp[w] will have at least list of elements representing the combination(s). If dp[w] is empty that would mean that there exists no such combination that sum up to w.
  
  If an element is greater than w then we cannot include that element. Otherwise, we have two options: (1) include one or more instances of the element, or (2) do not include it at all. Since this is not an optimization problem and we are interested in calculating the total count of all possible valid combinations we would count the combinations for both the inclusion (including one or more of an element) and exclusion (not including an element) situation.
  
  
• It is super important to determine how the inner and outer loop would look for this problem.
  Here is how we would leverage the optimal substructure property here:
  We would gradually increase the length of the prefix (contiguous array starting from index 0) of the given candidates[] array of items and calculate the DP results (valid combinations, in this case) for each weight starting from 0 to Target.

  
  for (int item = 0; item < candidates.length; item++) {
      for (int t = 0; t <= target; t++) {
          if (candidates[item] <= t) {
              ...
              ...
              }
          }
      }
  }
              
  

  
  
  We cannot change the order of the inner loop and outer loop because when we are calculating for DP result for subarray candidates[0...i] we cannot use the DP results for the entire array candidates[0...(n - 1)]. We are processing substructure, in this subarray or prefix array, candidates[0...i] we need to do all calculations based on the DP results gotten so far for candidates[0...i]. So the below code snippet would give wrong answer:
  

  
  for (int t = 0; t <= target; t++) {
      for (int item = 0; item < candidates.length; item++) {
          if (candidates[item] <= t) {
              ...
              ...
              }
          }
      }
  }
          

Please be familiar with the template of the space optimized solution in Unbounded Knapsack Problem before looking at the solution below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Space Optimized Solution using DFS :

DP Path = The path that led to the result in Dynamic Programming.

The approach that we are going to take in this solution is going to be the general approach to find DP paths. In this problem DP paths are all the combinations. This is a very common approach where we keep the corresponding parent pointers for each element in the DP paths. These parent pointers help in constructing all the DP paths or combinations in this case. Parent(s) of an element E2 is/are nothing but the element that precedes immediately in the DP path. So, if a combination is [E1, E2] then parent of E2 is E1. Since E1 has no parent we can mark that, say, -1.
In many cases, as in this problem, one element can be part of more than one DP paths. So an element can have more than one parent.

After we have constructed the parents[] array (or any other appropriate data structure) containing all the parents information, we start from the end of the DP paths (why? because as we will see we would know the ends of the paths, but we won't have enough information to know the beginning of the paths without doing a backtracking from the end element of the path) and do a DFS (Depth Search Search) to find all the DP paths. Think of the end elements of the DP paths as the leaf nodes in tree(s). All the DP paths would form a Forest.

The skeleton of the below code is same as that of the above code. We are keeping a data structure to track parents for element belonging to a combination. Using Unbounded Knapsack Concept, whenever we see that we can successfully include one element in a combination, we immediately store the node that would be preceding it in the combination in the parent data structure. After the parent data structure has been constructed and populated, we do a DFS and discover all the combinations.

I have put all the implementation details, like all nitty gritty stuff, in the inline comments in the code below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Tip:

Often times if a problem mentions that you can include an element as many time as you want, there is a chance that the problem could be solved using Unbounded Knapsack Concept.

Instructor: