Simple and clean Java code, backtracking.


  • 58
    J
     public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        combination(ans, new ArrayList<Integer>(), k, 1, n);
        return ans;
    }
    
    private void combination(List<List<Integer>> ans, List<Integer> comb, int k,  int start, int n) {
    	if (comb.size() == k && n == 0) {
    		List<Integer> li = new ArrayList<Integer>(comb);
    		ans.add(li);
    		return;
    	}
    	for (int i = start; i <= 9; i++) {
    		comb.add(i);
    		combination(ans, comb, k, i+1, n-i);
    		comb.remove(comb.size() - 1);
    	}
    }

  • 0
    Z

    great. short and elegant. !


  • 34
    T

    To make this faster, you can quit the for loop early and avoid unnecessary work.

        private static void combination(List<List<Integer>> ans, List<Integer> comb, int k,  int start, int n) {
            if (comb.size() > k) {
                return;
            }
            if (comb.size() == k && n == 0) {
                List<Integer> li = new ArrayList<Integer>(comb);
                ans.add(li);
                return;
            }
            for (int i = start; i <= n && i<=9; i++) {
                    
                    comb.add(i);
                    combination(ans, comb, k, i+1, n-i);
                    comb.remove(comb.size() - 1);
                
            }
        }
    

    if you think for loop with multiple conditions is complex, you can add an if condition inside the for loop instead.

    private static void combination(List<List<Integer>> ans, List<Integer> comb, int k,  int start, int n) {
            if (comb.size() > k) {
                return;
            }
            if (comb.size() == k && n == 0) {
                List<Integer> li = new ArrayList<Integer>(comb);
                ans.add(li);
                return;
            }
            for (int i = start; i<=9; i++) {
                   if (n-i >= 0) {
                       comb.add(i);
                       combination(ans, comb, k, i+1, n-i);
                       comb.remove(comb.size() - 1);
                   }
    
            }
        }
    

  • 4
    W

    Great solution! But I still have a question about

    List<Integer> li = new ArrayList<Integer>(comb);
    

    Why we can't list.add(comb) directly? I tried that, but the result is wrong.
    And I tried ans.addAll(comb), it showed me " no suitable method found for addAll(List<Integer>) " But list indeed has this method. Could you explain that? Thank you so much in advance.


  • 7
    S

    Because comb will continue being modified. You want to put a copy of comb in result instead


  • 0
    D
     if (comb.size() > k) {
            return;
        }
    

    Good work!


  • 0
    Z

    Good explanation!


  • 0
    W
    This post is deleted!

  • 0
    W

    Good solution, thank you! Could you please tell me why do you create extra list before adding comb to result, here :

    List<Integer> li = new ArrayList<Integer>(comb);

    I tested, that without doing so, empty lists will be added to the result. However, I don`t understand why it is so.


  • 1
    S

    Hi WElise,
    Hope it's not too late.
    if without doing so, the whole time, you will use just one Arraylist object, so it can be change by "comb.remove(comb.size() - 1);" after it is added to the "ans", it can be changed too.
    So, you will get a empty lists.


  • 0
    E

    @jinwu I think it's great way.But why it's so slow ,it only beat only 13% .


  • 0
    O

    Nice solution , I have a problem about the difference between next two code :

     combination(ans, comb, k, i+1, n-i);
    

    and

     combination(ans, comb, k, start+1, n-i);
    

  • 0
    M

    @wwtwxlwjh List<Integer> li = new ArrayList<Integer>(comb) will copy comb to a new memory space. Besides, comb will be modified later. So if you just add comb to list, list will just make a pointer pointing to comb instead of making a new memory space. So if comb is modified, list will be modified too.


  • 0
    U

    @topcoder4309 said in Simple and clean Java code, backtracking.:

    if (comb.size() > k) {
    return;
    }
    if (comb.size() == k && n == 0) {
    List<Integer> li = new ArrayList<Integer>(comb);
    ans.add(li);
    return;
    }

    Isn't this better? Reduces one more call.

        if (comb.size() == k && n == 0) {
            List<Integer> li = new ArrayList<Integer>(comb);
            ans.add(li);
            return;
        } else if (comb.size() == k) {
            return;
        }

  • 2
    M

    @topcoder4309 In fact we can combine 'if(n-i>=0)' with the 'comb.size()>k' in the beginning, and it will become:
    private static void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
    if (comb.size() > k || n<0) {
    return;
    }
    if (comb.size() == k && n == 0) {
    List<Integer> li = new ArrayList<Integer>(comb);
    ans.add(li);
    return;
    }
    for (int i = start; i<=9; i++) {
    comb.add(i);
    combination(ans, comb, k, i+1, n-i);
    comb.remove(comb.size() - 1);
    }
    }


  • 2
    C

    What is the time complexity of this solution?


  • 0
    Z

    @chintant I think it is 9 * 8 * ... (9-k+1), which is factorial time, because we would try 9-i+1 possible numbers in ith step. If I were wrong, please point me out.


  • 0
    C

    @ZhuEason I think it is O(n.2^n), where n is 9, since only numbers from 1 to 9 can be used.
    consider if k>=9 then there will be 2^9 times combination method will be called by this code and each combination method takes O(n) time to add the Elements of the comb list. This is the worst time complexity. However I am not able to understand If k is less than 9 then what will be the average time complexity?
    Technically you can also argue that since n can never be greater than 9 its time complexity is O(1).


  • 0
    Z

    I think this is DFS instead of backtracking because it loops through all the possible results;


  • 0
    C

    adding the judge of " if (target < 0) return;" should reduce some work in some situation. eg,when n can be summed to with 0ne or two number.

    public class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
            
            List<List<Integer>> result = new ArrayList<>();
            
            if (k<=0 || n <= 0) return result;
            
            backTrack(k, n, 1, result, new ArrayList<Integer>());
            
            return result;
        }
        
        private void backTrack(int k, int target, int beginIdx, List<List<Integer>> result, List<Integer> record) {
            
            if (target < 0) {
                return;
            }
            
            if (record.size() == k) {
                if (target == 0) {
                    result.add(new ArrayList<Integer>(record));
                }
                return;
            }
            
            for (int i=beginIdx; i < 10; i++) {
                record.add(i);
                backTrack(k, target - i, i + 1, result, record);
                record.remove(record.size() - 1);
            }
        }
    }
    

Log in to reply
 

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