Fast, easy Java code, with explanation!


  • 17
    S

    Used backtracking to solve this.
    Build an array to apply to "subset" template. Each time we add an element to the "list", for the next step, target= target - num[i]. Since we have already added one element, for the next step, we can only add k-1 elements. Since no duplicated elements accept, for the next loop, the "start" should point to the next index of current index. The list.remove(list.size() - 1) here means, we need to change the element here. I know it is hard to understand it, let me give you an example.
    When k=3, n=9, my answer works like this:
    [1]->[1,2]->[1,2,3]. Since now sum is not 9, no more backtracking, so after list.remove(list.size() - 1), it is [1,2]. Then next follows [1,2,4], sum is not 9, repeat process above untill [1,2,6]. When go to next backtracking, the list will be added to result, and for this list, no more backtracking.
    Now we can go back to a previous backtracking, which is [1,3]->[1,3,4], fail. [1,4,]->[1,4,5], fail. And so one.
    So the point of list.remove(list.size() - 1) is, after each "fail" or "success", since we don't need to do further attempts given such a condition, we delete the last element, and then end current backtracking. Next step is, add the next element to the deleted index, go on attempting.

    If you have other questions, just reply me.

    public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] num = {1,2,3,4,5,6,7,8,9};
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(result, new ArrayList<Integer>(), num, k, n,0);
        return result;
        }
    
    public void helper(List<List<Integer>> result, List<Integer> list, int[] num, int k, int target, int start){
        if (k == 0 && target == 0){
            result.add(new ArrayList<Integer>(list));
        } else {
            for (int i = start; i < num.length && target > 0 && k >0; i++){
                list.add(num[i]);
                helper(result, list, num, k-1,target-num[i],i+1);
                list.remove(list.size()-1);
            }
        }
    }
    

    }


  • 3
    B

    Thank you for your explanation! Could you please tell me why we need "result.add(new ArrayList<Integer>(list));" rather than "result.add(list);"?


  • 0
    S

    I am not sure, but I guess after you add the current list to result, you still need to use that list, so if you directly add it to result, when you change list, the data in result may also be changed since they refer to the same object.


  • 0
    Z

    Thank you for your explanation!


  • 0
    R

    @bumblebeem said in Fast, easy Java code, with explanation!:

    Thank you for your explanation! Could you please tell me why we need "result.add(new ArrayList<Integer>(list));" rather than "result.add(list);"?

    Same question.


  • 2
    S

    @Rhodey so the reason you need it is because list is an object which you are always adding and removing from. If you add that object to result, that object is still the same object being referenced which you are adding and removing to. You thus need to create a new list object each time you obtain a solution.

    In order words ArrayList<ArrayList<Integer>> is a list of ArrayList<Integer> objects simply adding result.add(list) you would be adding the same list object over and over. And since each of those list is always the same object (they all point to the same list object) they would all look the same in the end, in this case empty since you always remove the element you add to the list.

    Hopefully that makes sense. Let me know if it doesn't I can try to clear it up for you.


  • 0
    2
    public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> res = new ArrayList<>();
            if(k < 1 || k > 9 || n < 1 || n > 45)   return res; // the max of n is sum(1 to 9);
            List<Integer> list = new ArrayList<>();
            int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
            help(k, n, nums, res, list, 0);
            return res;
        }
        public void help(int k, int target, int[] nums, List<List<Integer>> res, List<Integer> list, int start) {
            if(k == 0 && target == 0) {
                res.add(new ArrayList<Integer>(list)); //list will be emptied, should add the copy of it
            }
            for(int i = start; i < nums.length && target > 0 && k > 0; i++) {
                list.add(nums[i]);
                help(k - 1, target - nums[i], nums, res, list, i + 1); //i + 1 not target + 1;
                list.remove((Integer)nums[i]); // Class ArrayList overload function: remove(int index) remover(Object o)
            }
            
        }
    

  • 0
    F

    Same idea without using loop.

    public class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> list = new ArrayList<>();
            helper(list,1,0,k,n,new ArrayList<Integer>(),0);
            return list;
        }
        public void helper(List<List<Integer>> list,int num, int count, int k,int target, List<Integer> list2, int sum){
            if(count == k && sum == target){
                List<Integer> li = new ArrayList<Integer>(list2);
                list.add(li);
            }
            else if(num <=9){
                list2.add(num);
                helper(list,num+1,count+1,k,target,list2,sum+num);
                list2.remove(list2.size()-1);
                helper(list,num+1,count,k,target,list2,sum);
            }
        }
    }
    

  • 0
    S

    Thank you for your explanation!!!


Log in to reply
 

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