Easy java solution using backtracking


  • 0
    I
    public class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<>();
            List<Integer> cur = new ArrayList<>();
            Arrays.sort(candidates);
            backtracking(ans, cur, candidates, 0, target);
            return ans;
            
        }
        
        public void backtracking(List<List<Integer>> ans, List<Integer> cur, int[] candidates, int pos, int target) {
            if(target == 0) {
                ans.add(new ArrayList<Integer>(cur));
                return;
            }
            if(pos >= candidates.length || target < 0) return;
            cur.add(candidates[pos]);
            backtracking(ans, cur, candidates, pos + 1, target - candidates[pos]);
            cur.remove(cur.size() - 1);
            pos++;
            while(pos < candidates.length && candidates[pos] == candidates[pos - 1]) pos++;
            backtracking(ans, cur, candidates, pos, target);
        }
    }
    

Log in to reply
 

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