Java backtracking solution


  • 0
    M
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<List<Integer>> ();
            List<Integer> list = new ArrayList<Integer>();
            combSum_recursion(0, 0, candidates, target, res, list);
            return res;
        }
        
        private void combSum_recursion(int index, int sum, int[] candidates, int target, List<List<Integer>> res, List<Integer> list){
            if(sum==target){
                res.add(new ArrayList<Integer>(list));
            } else if(sum<target) {
                for(int i=index; i<candidates.length; i++){
                    list.add(candidates[i]);
                    sum += candidates[i];
                    combSum_recursion(i, sum, candidates, target, res, list);
                    sum -= candidates[i];
                    list.remove(list.size()-1);
                }
            }
        }
    }
    
    

Log in to reply
 

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