Very Short Java Solution with Thoughts


  • 0
    Y

    The key idea is to sort the array first. I tried to solve it without sorting, and found it extremely difficult handling cases such as [2, 2, 2], target = 4 or [1, 2, 1, 5], target = 8. If we sort the array, everything suddenly comes together nicely. Whenever we see arr[i] == arr[i-1] we simply skip the same numbers. This also handles the case such as [2, 2, 2], target = 4 quite well. We first try searching for solutions using the first appearances of 2's, and then skip the rest.

    public class Solution {
        private List<List<Integer>> L = new ArrayList<>();
        
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            search(candidates, target, 0, 0, new ArrayList<>());
            return L;
        }
        
        private void search(int[] arr, int target, int start, int sum, List<Integer> list) {
            if (sum == target) {
                L.add(new ArrayList<>(list));
                return;
            }
            for (int i = start; i < arr.length; i++) {
                if (i > start && arr[i] == arr[i-1]) {
                    continue;
                }
                if (sum + arr[i] <= target) {
                    list.add(arr[i]);
                    search(arr, target, i+1, sum+arr[i], list);
                    list.remove(list.size()-1);
                }
            }
        }
    }
    

Log in to reply
 

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