My thoughts and solution to the problem -Java


  • 3
    B

    Hello, I've solve the problem and I am here to give back to the community. Basically the question is pretty straight forward. I've approached the problem with sorting the array first, and keeping the current value and make recursive call to check for target - current value. Any suggestion on how I can make this code better is much appreciated. Thank you.

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] num, int target) {
            if(num.length==0) return new ArrayList<List<Integer>>();
            Arrays.sort(num); //sort the array of num so it's easier to manage
            List<List<Integer>> result = helper(num,target,0);
            if(result==null) return new ArrayList<List<Integer>>();
            return result;
        }
        public List<List<Integer>> helper(int[] num, int target, int index)
        {
            if(index>=num.length||num[index]>target) return null; //return null if you hit the end
            ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
            ArrayList<Integer> temp = new ArrayList<Integer>();
            Set<List<Integer>> s = new HashSet<List<Integer>>(); //check if there is no duplicates
            for(int i = index;i<num.length;i++)
            {
                 //if num[i]> target you dont need to check the rest. 
                 //but it's break here because you still want to keep the rest of the result.
                if(num[i]>target) break; 
                temp = new ArrayList<Integer>();
                //if it's found the rest of the numbers can be trimed, save some time on complexity
                if(num[i]==target) 
                {
                    temp.add(num[i]);
                    result.add(temp);
                    return result;
                }
                ArrayList<List<Integer>> t = (ArrayList)helper(num,target-num[i],i+1);
                //t is the temporary ArrayList of the result of your recursion call
                // you want to add the value of your current num[i] in the beginning of each
                // returned List<Integer> and add it to result if it's not duplicated.
                if(t!=null)
                {
                    for(List<Integer> a:t)
                    {
                        a.add(0,num[i]);
                        if(!s.contains(a)) //make sure there is no duplicates
                        {
                            s.add(a);
                            result.add(a);
                        }
                    }
                }
            }
            return result;
        }
    }

  • 0
    S

    the s.contains(a) takes O(n) time to check all the elements in s, so it may create time limit exceed problem.
    Such as in 3Sum problem (quite similar to this problem).

    This Combination sum does not has time limit exceed problem, I think it is because this Combination sum
    takes O(n!) time itself.

    I am not sure what I thought is right. Just for your reference.
    Below is my way to avoid to use contains. It is quite similar to your solution

    public List<List<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num); 
        return combinationSum(num,target,0);
    }
     public List<List<Integer>> combinationSum(int[] num, int target, int index){
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(target<=0) return result; //all the numbers all positive..no need to check left has 0 or negitive number
        int previouscheck=Integer.MIN_VALUE;
        for(int i=index;i<num.length;i++){
            if(previouscheck==num[i]) continue; // if the same value num[i] has been checked before..skip it
            previouscheck=num[i];
            if(num[i]>target) break; // all left are bigger than target..
            if(num[i]==target){
                List<Integer> cur=new ArrayList<Integer>();
                cur.add(num[i]);
                result.add(cur);
                return result;
            }
            List<List<Integer>> lastreturn=combinationSum(num,target-num[i],i+1);
            if(!lastreturn.isEmpty()){
                for(List<Integer> cur:lastreturn){
                    cur.add(0,num[i]);
                    result.add(cur);
                }
            }
        }
        return result;
    }

  • 0
    R

    Even though you do not use contain function. cur.add(0,num[i]) insert a number at the begin of an arraylist. That takes O(n) time too because array has to shuffle all elements behind.


Log in to reply
 

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