Beat 93.63% solutions + Questions in complexity analysis


  • 0

    Here is my java solution, and this link (Leetcode Solution 39) gives the detail explanation.

    If you have some question, welcome to let me know. And hope you guys can help me to check me complexity part. The following is my solution but don't know if it is correct!

    Thank you and best wishes!!!

    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 an array.

    • Space complexity : $O(log(n))$.


Log in to reply
 

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