Using Backtracking, classic coin change problem


  • 0
    R
    public class Solution {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            combinationSum(candidates, target, 0, new ArrayList<Integer>());
            return result;
        }
        
        private void combinationSum(int[] candidates, int target, int index, ArrayList<Integer> sofar) {
            if(target == 0) {
                result.add(new ArrayList<Integer>(sofar));
                return;
            }
            
            if(target < 0) return;
            if(index >= candidates.length) return;
            
            // include current candidate
            sofar.add(candidates[index]);
            combinationSum(candidates, target - candidates[index], index, sofar);
            sofar.remove(sofar.size()-1);
            
            // don't include current candidate
            combinationSum(candidates, target, index+1, sofar);
        }
    }

Log in to reply
 

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