A simple easily understanding JAVA solution by using backtracking without using set.


  • 0

    To ensure without duplicates combinations, make sure that in each combination the elements should be in ascending order. for example [2,2,3] is one of the combination of the target answer, however, [3,2,2] is not since it is not in ascending order.

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (candidates == null || candidates.length == 0){
                return res;
            }
            List<Integer> com = new ArrayList<>();
            backtrack(candidates, target, com, res);
            return res;
        }
        private void backtrack(int[] candidates, int target, List<Integer> com, List<List<Integer>> res){
            if (target == 0){
                
                res.add(new ArrayList<>(com));
                return;
            }
            if (target < 0){
                return;
            }
            for (int i = 0; i < candidates.length; i++){
                if (com.size() > 0 && candidates[i] < com.get(com.size() - 1)){
                    continue;
                }
                com.add(candidates[i]);
                backtrack(candidates, target - candidates[i], com, res);
                com.remove(com.size() - 1);
            }
        }
    }
    

Log in to reply
 

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