C ++ Remove Duplication in List Set

Question

I am trying to remove duplicates in the return list in this question

For a set of candidate numbers (C) and target number (T), find all unique combinations in C, where the numbers of candidates are summed with T.

Each number in C can be used only once in combination.

Note:

• All numbers (including the target) will be positive integers.

• Elements in combination (a1, a2, ..., ak) must be in descending order. (i.e. a1 ≤ a2 ≤ ... ≤ ak).

• The solution set must not contain duplicate combinations.

For example, this set of candidates 10,1,2,7,6,1,5 and target 8, a set of solutions:

[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

My question is how to remove duplication effectively? Below is my code:

public class Solution {
    public static void main(String[] args) {
        int[] input = { 10, 1, 2, 7, 6, 1, 5 };
        // int[] input = { 2, 1, 1, 4, 4, 2 };
        System.out.println(combinationSum2(input, 8));
    }

    private static class Entry {
        List<Integer> list;
        int target;
        int index; // the previous index

        public Entry(int target) {
            list = new LinkedList<Integer>();
            this.target = target;
        }

        public int add(int num, int index) {
            this.list.add(num);
            this.index = index;
            this.target -= num;
            return target;
        }

        public Entry copy() {
            Entry copy = new Entry(this.target);
            copy.list = new ArrayList<>();
            copy.list.addAll(list);
            copy.target = target;
            copy.index = index;
            return copy;
        }

    }

    public static List<List<Integer>> combinationSum2(int[] input, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();

        if (null == input || input.length <= 0)
            return ret;

        Arrays.sort(input);

        int N = input.length;
        Queue<Entry> pool = new LinkedList<Entry>();
        for (int i = 0; i < N; i++) {
            if (input[i] <= target) {
                Entry entry = new Entry(target);
                entry.add(input[i], i);
                pool.add(entry);
            }
        }

        while (!pool.isEmpty()) {
            Entry cur = pool.poll();
            if (cur.target == 0) {
                ret.add(cur.list);
            } else if (cur.target > 0) {
                for (int i = cur.index + 1; i < N; i++) {
                    if (cur.target - input[i] >= 0) {
                        Entry copy = cur.copy();
                        copy.add(input[i], i);
                        pool.offer(copy);
                    } else {
                        break;
                    }
                }
            }
        }

        return ret;
    }
}

- , , . ? ?

Answer 1

- HashSet . , , equals hashCode Entry. ( )

private static class Entry {
    List<Integer> list;
    int target;
    int index;
    int hash; // <---- add this

    public Entry(int target) {
        list = new LinkedList<Integer>();
        this.target = target;
        hash = target;
    }

    public int add(int num, int index) {
        this.list.add(num);
        this.index = index;
        this.target -= num;
        hash = hash * 17 + num;
        return target;
    }

    public Entry copy() {
        Entry copy = new Entry(this.target);
        copy.list = new ArrayList<>();
        copy.list.addAll(list);
        copy.target = target;
        copy.index = index;
        copy.hash = hash;
        return copy;
    }

    @Override
    public boolean equals(Object obj) {
        Entry e = (Entry) obj;
        if ((this.target != e.target) || (this.list.size() != e.list.size())) {
            return false;
        }
        for (int i = 0; i < this.list.size(); i++) {
            if (!this.list.get(i).equals(e.list.get(i)))
                return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        return hash;
    }
}

- .

Set<Entry> nodup = new HashSet<Entry>();

while (!pool.isEmpty()) {
    Entry cur = pool.poll();
    if (cur.target == 0) {
        nodup.add(cur);
    } else if (cur.target > 0) {
        // ... your code
    }
}

for (Entry entry : nodup) {
    ret.add(entry.list);
}

Answer 2

Java, List HashSet Java. , , Set , List, List Set Java.

, List HashSet, , .

Answer 3

, O(n) ( ).

, . , - (HashSet): , ; .