Java Backtracking, classical coin change algorithm


  • 0
    R
    public class Solution {
        HashSet<List<Integer>> result = new HashSet<List<Integer>>();
        
        public List<List<Integer>> combinationSum3(int k, int n) {
            combinationSum3(k, n, 1, new ArrayList<Integer>());
            return new ArrayList<List<Integer>>(result);
        }
    
        /*
            k = subset length
            n = target sum
            number = current number to consider ( 1 - 9 only)
            sofar = sofar subset (we can't use same number in subset)
        */
        private void combinationSum3(int k, int n, int number, ArrayList<Integer> sofar) {
            if(n == 0 && sofar.size() == k) {
                result.add(new ArrayList<Integer>(sofar));
                return;
            }
            
            if(n < 0) return;
            if(number > 9) return;
            if(sofar.size() > k) return;
            
            // include current number
            sofar.add(number);
            combinationSum3(k, n-number, number+1, sofar);
            sofar.remove(sofar.size()-1);
            
            // exclude current number
            combinationSum3(k, n, number+1, sofar);
        }
    }

Log in to reply
 

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