Beats 95%


  • 0

    Java

    class Solution {
    	public List<List<Integer>> combinationSum2(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;
    				if(i > start && candidates[i] == candidates[i-1]) continue; 
    				temp.add(candidates[i]);
    				helper(candidates, tar - candidates[i], i + 1, res, temp);
    				temp.remove(temp.size() - 1);
    			}
    		}
    	}
    }
    

    Complexity Analysis
    Time complexity : (O(2^n)). where (n) is the number of elements in the array. Because we have to try all the (n) combinations

    Detail explanation: LeetCode Solution 39


Log in to reply
 

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