Explain why deduplication has to be done this way


  • 0
    L

    Many solutions posted here handle the deduplication with pointer moving correctly. But it's not so intuitive to explain why the pointer moving is correct. Here is my thought: when we invoke csum(arr, j+1, t-curr) recursively, all the ways the arr[j] element and its same values can appear will be visited, so what needs to be considered next are cases that don't use arr[j] anymore.

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] arr, int t) {
            Arrays.sort(arr);
            return csum(arr, 0, t);
        }
        
        List<List<Integer>> csum(int[] arr, int i, int t) {
            List<List<Integer>> ol = new ArrayList<List<Integer>>();
            if (t==0) {
                ol.add(new ArrayList<Integer>());
                return ol;
            }
            if (t<0 || i>=arr.length)
                return ol;
    
            int j=i;
            while (j<arr.length) {
                int curr = arr[j];
                List<List<Integer>> next = csum(arr, j+1, t-curr);
                for (List<Integer> al:next) {
                    List<Integer> bl = new ArrayList<Integer>(al);
                    bl.add(0, curr);
                    ol.add(bl);
                }
                int j0=j;
                while (j<arr.length && arr[j]==arr[j0]) j++;
            }
            
            return ol;
        }
    }

Log in to reply
 

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