Java backtracking solution based on Combination Sum, easy to understand


  • 0
    F

    The idea is to search for all the possible solution by backtracking, and only add buffer list into result list when the sum is equal to target and also the number of integer used is equal to candidate.
    I create a int array from 1 to 9 only to match my solution for Combination Sum I.

    In the recursion function combinationSum3Helper(int[] nums, int n, int index, int target)

    n is the candidates number.

    index is the index of int array from 1 to 9.

    Hope it helps.

    public class Solution {
        List<List<Integer>> res;
        Deque<Integer> tmp;
        public List<List<Integer>> combinationSum3(int candidates, int target) {
            res = new ArrayList<List<Integer>>();
            tmp = new ArrayDeque<Integer>();
            int[] nums = {1,2,3,4,5,6,7,8,9};
            combinationSum3Helper(nums, candidates, 0, target);
            return res;
        }
        
        public void combinationSum3Helper(int[] nums, int n, int index, int target){
            if(target == 0 && n == 0)
            {
                res.add(new ArrayList<Integer>(tmp));
                return;
            }
            
            if(index >= nums.length || target - nums[index] < 0 || n < 0) return;
            
            for(int i = index; i < nums.length; i ++){
                tmp.addLast(nums[i]);
                combinationSum3Helper(nums, n - 1, i + 1, target - nums[i]);
                tmp.removeLast();
            }
        }
    }

Log in to reply
 

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