DAY 11 - Combination Sum

Nayan Pahuja - Jun 14 '23 - - Dev Community

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-11.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

Problem 1: 39. Combination Sum

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example:

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.

Intuition:

In questions like combination or subsequences or sequences we can always use a recursion approach. In fact it should be the first thing that should strike our mind.

How to think in this question?
Well There are 2 options here. Let's say at start our index is at 0. Whether we pick the element or we do not.
If we do pick the element, we subtract the value from our target and add the element to combinational array.
If we do not pick the element, we just increment our index and rest everything stays same.
Then after calling the function, this will go through all possibilities and return our answer.
The most important part is to know when to break our function.
Well once we have traversed to the end of array, we can't have any more cases.
Hence This question was to be solved like this.

Base condition

If index== size of array and target == 0 include the combination in our answer

Code:

void findCombination(int ind, int target, vector < int > & candidates, vector < vector < int >> & result, vector < int > & comb) {
      if (ind == candidates.size()) {
        if (target == 0) {
          result.push_back(comb);
        }
        return;
      }
      // pick up the element 
      if (candidates[ind] <= target) {
        comb.push_back(candidates[ind]);
        findCombination(ind, target - candidates[ind], candidates, result, comb);
        comb.pop_back();
      }

      findCombination(ind + 1, target, candidates, result, comb);

    }
  public:
    vector < vector < int >> combinationSum(vector < int > & candidates, int target) {
      vector < vector < int >> result;
      vector < int > comb;
      findCombination(0, target, candidates, result, comb);
      return result;
    }
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis:

Time Complexity:O(2^t^N)
Space Complexity:O(n*x)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .