[LeetCode Solution 39]: Combination Sum

[LeetCode Solution 39]:  Combination Sum

*********************************************************************************

Question:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sum to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including the target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target,7
A solution set is: 

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

--------------------------------------------------------------------------------------------------

Approach Recursive Method

Intuition

Most problems like this, which requires the return of all the required solutions, can be solved by recursive and the thinking part is similar.
if you carefully study these topics are found in a routine, are required to write another recursive function, I always named this function as 'helper'.

In this problem, we explain use problem example, where candidate set [2, 3, 6, 7] and target 7, and try to find the solution:

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

We can consider this problem as the problem to find a tree path where the sum of tree node value on this path
is equal to target.

As shown in the picture which starts from value 2, and we find a path in the tree which is [2, 2, 3]. How can we find the path like that?
Depth First Search !!!.

Generally, we use the stack to implement DFS, so the following code is like this:

Java

class Solution {
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
  List<List<Integer>> res = new ArrayList<>();
  helper(candidates, target, 0, res, new ArrayList<>());
  return res;
 }
 
 public void helper(int[] candidates, int tar, int start, List<List<Integer>> res, List<Integer> temp)
 {
  if(tar < 0) return;
  else if(tar == 0) res.add(new ArrayList<>(temp));
  else
  {
   for(int i = start; i<candidates.length;i++)
   {
    temp.add(candidates[i]);
    helper(candidates, tar-candidates[i], i, res, temp);
    temp.remove(temp.size()-1);
   }
  }
 }
}

Complexity Analysis

• Time complexity : \(O(n)\). where \(n\) is the number of elements in an array. Because we have to visit all the tree node to get the path.
• Space complexity : \(O(log(n))\). The space complexity is related to the height of the 'Tree' which is \(O(log(n))\)

---

Can we do better?

Strategy

Every time we visit a node and we have to update the target value and then continue the recursive using the updated value.
But this case is not always necessary. Because when the node value which we visited is bigger than the target value
and we still doing the recursive is wasting time.

The modified code is as follows:

Java

class Solution {
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
  List<List<Integer>> res = new ArrayList<>();
  Arrays.sort(candidates);
  helper(candidates, target, 0, res, new ArrayList<>());
  return res;
 }
 
 public void helper(int[] candidates, int tar, int start, List<List<Integer>> res, List<Integer> temp)
 {
  if(tar < 0) return;
  else if(tar == 0) res.add(new ArrayList<>(temp));
  else
  {
   for(int i = start; i<candidates.length;i++)
   {
    if(candidates[i]>tar) break;
    temp.add(candidates[i]);
    helper(candidates, tar-candidates[i], i, res, temp);
    temp.remove(temp.size()-1);
   }
  }
 }
}

Complexity Analysis

• Time complexity : \(O(n)\). where \(n\) is the number of elements in the array. Because we have to visit all the tree node to get the path.
• Space complexity : \(O(log(n))\). The space complexity is related to the height of the 'Tree' which is \(O(log(n))\)

The Running results: