Easy to understand 96% performance Java solution


  • 7
    B
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            return combinationSum(candidates, target, 0);
        }
        
        public List<List<Integer>> combinationSum(int[] candidates, int target, int start) {
            
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            Arrays.sort(candidates);
            for (int i = start; i < candidates.length; i++) {
                if (candidates[i] <target) {
                    for (List<Integer> ar : combinationSum(candidates, target - candidates[i], i)) {
                        ar.add(0, candidates[i]);
                        res.add(ar);
                    }
                } else if (candidates[i] == target) {
                    List<Integer> lst = new ArrayList<>();
                    lst.add(candidates[i]);
                    res.add(lst);
                } else
                    break;
            }
            return res;
        }
    }

  • 0
    A

    Any leads to how I can calculate the time complexity for this solution?


  • 0
    W

    Good code!!Thank you


  • 0
    2

    @aswinmuthiah is the run-time O(N^2)? since every recursive call it'll traverse through the entire list?


  • 0
    J

    Follow your solution, this is the result. Do you know how to make the position of the data non-unique. Thanks.

    [2,3,6,7]
    7
    Output:
    [[2,2,3],[2,3,2],[3,2,2],[7]]
    Expected:
    [[2,2,3],[7]]


Log in to reply
 

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