Duplicate values in a hashSet

Question

I am trying to count the number of combinations of 1, 5, 10 and 25 that sum to n. Given that I don't want any repetitions (like 1+5 = 6 and 5+1 = 6). I am using a hashSet. I implemented a class named ResultSet that saves the number of 1, 5, 10, and 25 in a solution and I overrode the equals method. However, for some reason, my solution hashSet keeps returning duplicate values. Why?

import java.util.HashSet;

public class Solution {

  public static void main(String[] args) {
    int N = 6;
    int combinationsSolution = new Combine(N).getSolution();
    System.out.println("N= " + N + " Number of solutions= " + combinationsSolution);

  }
}

class Combine {

  private int solution;

  private int n;

  private HashSet<ResultSet> cacheUnordered = new HashSet<ResultSet>();

  public Combine(int N) {
    this.n = N;
    this.solution = solve(n);
  }

  public int getSolution() {
    return solution;
  }

  public int solve(int N) {
    solve(N, 0, 0, 0, 0);
    for (ResultSet r:cacheUnordered){
      System.out.println(r.toString());
    }
    return cacheUnordered.size();
  }

  public void solve(int N, int substracted1, int substracted5, int substracted10, int substracted25) {
    if (N == 0) {
      cacheUnordered.add(new ResultSet(substracted1, substracted5, substracted10, substracted25));
    } else if (N > 0) {
      solve(N - 1, substracted1 + 1, substracted5, substracted10, substracted25);
      solve(N - 5, substracted1, substracted5 + 1, substracted10, substracted25);
      solve(N - 10, substracted1, substracted5, substracted10 + 1, substracted25);
      solve(N - 25, substracted1, substracted5, substracted10, substracted25 + 1);
    }
  }
}

class ResultSet {
  private int numberOf1;

  private int numberOf5;

  private int numberOf10;

  private int numberOf25;

  public ResultSet(int num1, int num5, int num10, int num25) {
    numberOf1 = num1;
    numberOf5 = num5;
    numberOf10 = num10;
    numberOf25 = num25;
  }

  @Override
  public String toString(){
    String result;
    result = numberOf1 + " " + numberOf5 + " " + numberOf10 + " " + numberOf25;
    return result;
  }

  @Override
  public boolean equals(Object r2) {
    if (r2 == null) {
      return false;
    }
    if (!(r2 instanceof ResultSet)) {
      return false;
    }
    ResultSet rr = (ResultSet) r2;
    if (rr.numberOf1 == this.numberOf1 && rr.numberOf5 == this.numberOf5
            && rr.numberOf10 == this.numberOf10 && rr.numberOf25 == this.numberOf25) {
      System.out.println("Comparing " + this.toString() + " to " + rr.toString());
      return true;
    } else {
      return false;
    }
  }

  public int getNum1() {
    return numberOf1;
  }

  public int getNum5() {
    return numberOf5;
  }

  public int getNum10() {
    return numberOf10;
  }

  public int getNum25() {
    return numberOf25;
  }
}

score 5 · Accepted Answer · edited May 23 '17 at 10:24

5

For your ResultSet class, you defined an equals() method but not a hashCode() method. You need both methods for HashSet to work correctly. Please see this explanation. (It talks about HashMap, but it also applies to HashSet.)

edited May 23 '17 at 10:24

Community

1
1

answered Mar 10 '15 at 19:46

dbank

1,173
1
17
29

score 3 · Answer 2 · answered Mar 10 '15 at 19:55

As JavaDoc Clearly Specified

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

and you have not followed it , that is why you get duplicates ,

Please Read How HashCode and Equals Work it will help you out to understand the above statement better

Duplicate values in a hashSet

2 Answers2