Java AC Solution - Seeking further optimization


  • 0
    C

    I posted my recursive solution here, which took 232ms. The thought is straightforward: combinationSum of n = [1-9] + combinationSum of n-1, where [1-9] means one element between 1 and 9.
    Step by step:

    1. The base case is when k = 1, if n is within [1-9] then we could directly return this n. Otherwise return an empty list.

    2. Find maximum value used so far, which is stored in param "usedInt". I call it max.

    3. Start from max till 9, for each element we get a list of combinations. Add this element to each combination, then return result.

    4. IMPORTANT: I used HashSet here to eliminate possible duplicates. Before that, we need to sort each combination, i.e. insert element into its appropriate position. You can refer to the code below commented by "sort each list" and "remove duplicate".

    5. I AM NOT SATISFIED WITH MY CODE in terms of its length and thought. It is too long, and might be optimized by backtracking. However I am not sure how to do that. If anybody could help me figure out how to implement backtracking, or give a brief explanation, I will very appreciate it. Thank you:)

    public class Solution {
    	public List<List<Integer>> combinationSum3(int k, int n) {
    		List<List<Integer>> sets = new ArrayList<List<Integer>>();
    		if (k <= 0 || n < 1 || n > 45)
    			return sets;
    		HashSet<Integer> usedInt = new HashSet<Integer>();
    		List<List<Integer>> hasRepeat = combinationSum3(k, n, usedInt);
    		
    		// remove duplicate
    		HashSet<List<Integer>> noRepeat = new HashSet<List<Integer>>();
    		noRepeat.addAll(hasRepeat);
    		sets.addAll(noRepeat);
    		return sets;
    	}
    
    	private List<List<Integer>> combinationSum3(int k, int n,
    			HashSet<Integer> usedInt) {
    		List<List<Integer>> sets = new ArrayList<List<Integer>>();
    
    		// base case
    		if (k == 1 && n >= 1 && n <= 9 && !usedInt.contains(n)) {
    			List<Integer> set = new ArrayList<Integer>();
    			set.add(n);
    			sets.add(set);
    			return sets;
    		}
    		if (k == 1 || n < 1) return sets;
    
            // find maximum value used so far
    		int max = 0;
    		Iterator<Integer> it = usedInt.iterator();
    		while (it.hasNext()) {
    			int val = it.next();
    			if (val > max) max = val;
    		}
    		
    		// recursion
    		for (int i = max + 1; i <= 9; i++) {
    			HashSet<Integer> copy = (HashSet<Integer>) usedInt.clone();
    			copy.add(i);
    			List<List<Integer>> temp = combinationSum3(k - 1, n - i, copy);
    			for (int j = 0; j < temp.size(); j++) {
    				// sort each list
    				int index = 0;
    				for (; index < temp.get(j).size(); index++)
    					if (temp.get(j).get(index) > i) break;
    				temp.get(j).add(index, i);
    			}
    			// remove duplicate
    			if (!temp.isEmpty()) {
    				HashSet<List<Integer>> noRepeat = new HashSet<List<Integer>>();
    				noRepeat.addAll(temp);
    				sets.addAll(noRepeat);
    			}
    		}
    		return sets;
    	}
    }

  • 1
    R

    I went through your solution. I want to make a few comments.

    1. I like the way you put the upper limit for n. I didn't think of it, when I was solving this problem. Though we can extend the maximum limit logic based on the value of k, it becomes a lot of code. I like the way it is.

    2. It appears that you are creating the the list sets in the helper method, which runs recursively. Why don't you create the list in your first method and pass it to the helper? It would avoid creation of the list multiple times.

    3. You can send the highest element in the set as a parameter in your helper method, rather than finding it every time.

    4. You don't have to sort the list or use a HashSet to track the used numbers, if you code it a little differently.

    I made a few changes to your code, implementing the ideas in my comments 3 and 4. There isn't much improvement in the run time (I think that this is mainly because the limitations of the problem such as each element <=9. i.e the problem cannot force you to run in worst time as long as your program is decent. Please correct me if I am wrong.). But I think that the modified program is much readable and it avoids unnecessary sorting and removing of duplicates. Please find it below.

    public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> sets = new ArrayList<List<Integer>>();
            if (k <= 0 || n < 1 || n > 45)
                return sets;
            sets = combinationSum3(k, n, 0);
            return sets;
        }
    
        private List<List<Integer>> combinationSum3(int k, int n,
                int max) {
            List<List<Integer>> sets = new ArrayList<List<Integer>>();
    
            if (k == 1 && n>max && n<=9) {
                List<Integer> set = new ArrayList<Integer>();
                set.add(n);
                sets.add(set);
                return sets;
            }
            if (k == 1 && n > 9) return sets;
    
            for (int i = max + 1; i <= 9; i++) {
                List<List<Integer>> temp = new ArrayList<List<Integer>>();
                if(n>i) {
                    temp = combinationSum3(k - 1, n - i, i);
                    for (int j = 0; j < temp.size(); j++) {
                        temp.get(j).add(0, i);
                    }
                }
                sets.addAll(temp);
    
            }
            return sets;
        } 
    

    Please let me know if you have any questions. Also, if you want a reference for the idea in my 2nd comment, please check my code below. It avoids the need for copying lists.

    public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> list = new ArrayList<List<Integer>>();
            if(k==0) return list;
            combinationSumHelper(k,n,list,new ArrayList<Integer>(),0);
            return list;
        }
        private void combinationSumHelper(int k, int n, List<List<Integer>> list,List<Integer> current, int top) {
            for(int i=top+1;i<=9;i++) {
                if(k==1) {
                    if(i==n) {
                        current.add(i);
                        list.add(new ArrayList<Integer>(current));
                        current.remove(current.size()-1);
                        break;
                    }
                    else if(i>n) break;
                }
                else {
                    if(2*i<n) {
                        current.add(i);
                        combinationSumHelper(k-1,n-i,list,current,i);
                        current.remove(current.size()-1);
                    }
                    else break;
                }
            }
        }

  • 0
    C

    Thank you so much @Ravikanth , your comments and code are very helpful!


Log in to reply
 

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