My easy to understand dfs backtracking solution


  • 0
    T
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(candidates);
            if(candidates.length == 0 || target == 0) return result;
            
            helper(candidates, target, 0,result, new ArrayList<Integer>() );
            return result;
        }
        
        public void helper(int[] nums, int target, int start, List<List<Integer>> result, List<Integer> list){
            
            if(target == 0){
                List<Integer> temp = new ArrayList<>(list);
                if(!result.contains(temp)){
                    result.add(temp);
                }
                return;
            }
            if(start>=nums.length) return;
            for(int i=start;i<nums.length;i++){
                if(target-nums[i]>=0){
                    list.add(nums[i]);
                    helper(nums, target-nums[i], i+1, result,list);
                    list.remove(list.size()-1);
                }else return;
            }
        }
    }

Log in to reply
 

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