Solution by monkeykingyan


  • 0

    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.

    Screen Shot 2017-09-16 at 6.11.36 PM.png

    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 a 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 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))$


    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))$


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.