C++의 모든 고유 한 조합을 찾아, 내가 후보 번호 (C)과 대상 번호 (T)의 집합을 감안할 때 <a href="https://oj.leetcode.com/problems/combination-sum-ii/" rel="nofollow">this question</a></p> <p>에 반환 목록에서 중복을 제거하기 위해 노력하고있어

Question

목록의 집합에 중복 제거 후보 번호가 T와 합계하는 C.

C의 각 숫자는 조합에서 한 번만 사용할 수 있습니다.

참고 : (대상 포함)

1. 모든 숫자는 양의 정수가 될 것입니다.

2. (a1, a2, ..., ak) 조합의 요소는 내림차순이 아니어야합니다. (즉, a1 ≤ a2 ≤ ... ≤ ak).

3. 솔루션 세트에는 중복 조합이 없어야합니다.

예를 들어, 주어진 후보가 10,1,2,7,6,1,5 및 대상 (8)을 설정, 해결책 집합은 다음과 같습니다

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

내 질문은 효율적으로 제거하는 방법입니다 복제? 다음은 내 코드입니다 :

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을 사용하여 기존 엔트리를 추가하지 않는 것이다. 가장 먼저 할 일은 Entry 클래스의 equals 및 hashCode 함수를 재정의하는 것입니다. (more material)

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

다른 솔루션으로는 해시를 사용할 수 있지만 공간적으로 (동일한 경우) O(n)을 사용합니다.

본질적으로 목록에서 목을 따라 이동하십시오. 새로 발견 된 모든 요소에 대해 해시 집합 (HashSet)에 있는지 여부를 확인합니다. 그렇다면 제거합니다. 그렇지 않으면 우리는 그것을 넣는다.

Answer 3

당신은 자바 HashSet의에 목록을 변환하여 중복 또는 Java에서 목록에서 반복되는 요소를 제거 할 수 있습니다. 그러나 그 일을하기 전에 Set은 List에 의해 보장되는 삽입 순서를 유지하지 않는다는 사실을 명심하십시오. 사실 그것은 List와 Set의 주요 차이점입니다.

그래서 List를 HashSet으로 변환하면 모든 중복 요소가 제거되지만 삽입 순서는 손실됩니다.

자세한 내용은 찾을 수 있습니다. here