java backtracking solution


  • 0
    P
    class Solution {
        List<List<Integer>> list = new ArrayList<>();
        int[] candidates;
        int target;
        int sum = 0;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            this.candidates = candidates;
            this.target = target;
            List<Integer> sublist = new ArrayList<>();
            recursive(sublist,0);
            return list;
        }
        public void recursive(List<Integer> sublist,int index)
        {
            if(sum>target)
            {
                return;
            }
            if(sum == target)
            {
                list.add(new ArrayList<Integer>(sublist));
                return;
            }
            for(int i = index;i<candidates.length;i++)
            {
                //System.out.println("sum = " + sum);
                //System.out.println("sublistpre = "+sublist);
                sum += candidates[i];
                sublist.add(candidates[i]);
                //System.out.println("sublistafter = "+sublist);
                recursive(sublist,i);
                sublist.remove(sublist.size()-1);
                sum -= candidates[i];
            }
            return;
        }
    }
    

Log in to reply
 

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