6
\$\begingroup\$

I am printing subsets from an array whose sum has been specified, while avoiding duplicates.

I think there may be improvements, potentially on how using map is bad idea, or how can I avoid map to filter the duplicates.

Additionally, in my code I want to reverse the sort order of an int array using streams which is asked over here, are there any alternatives rather than sorting and reversing the array?

public class FindSubSetArray {

    private static final int TARGET_SUM = 24;
    private static Map<String,Integer> subSet = new HashMap<>();
    private static int count = 0;

    public static void main(String[] args) {
        int[] array= {2, 5, 1, 2, 4, 1, 6, 5, 2, 2};
        Arrays.sort(array);
        findSubset(array, 0, 0, "");
        subSet.keySet().stream().forEach(System.out::println);
    }

    public static void findSubset(int[] array, int index, int current, String subSetString) {

        if (current > TARGET_SUM || array.length < index) return;

        for (int i = index; i < array.length; i++) {
            int presentSum = current + array[i];
            if (presentSum == TARGET_SUM) {
     //         System.out.println(subSetString + " " + array[i]);
                subSet.put(subSetString + " " + array[i], count++);
            } else {
                findSubset(array, i + 1, presentSum, subSetString + " " + array[i]);
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Can you clarify exactly what you are trying to accomplish? I find it hard to understand your goal. Maybe an example? \$\endgroup\$ – Diego Martinoia Jan 18 '16 at 15:38
  • \$\begingroup\$ Above code is to find the sub array from a given array whose some is "24" in that process i might get duplicates based on the given array of elements. SO to avoid it i have used map. Is there a better algorithm to do or avoid map and improve my code. I am asking for suggestions to improve my code. \$\endgroup\$ – mallikarjun Jan 20 '16 at 13:11
  • \$\begingroup\$ Does your array only contains >= 0 values? Or can it also have negatives? because it makes quite the difference! \$\endgroup\$ – Diego Martinoia Jan 20 '16 at 13:22
  • \$\begingroup\$ I can't see how your hashmap does the job – but possibly I just do not understand the job. What are 'duplicates' you're trying to avoid? Certainly "2 1" and "2 1" would be duplicates even if the first one is taken from positions 0 and 2, and the other one from 3 and 5. But are "2 1" and "1 2" considered duplicates? \$\endgroup\$ – CiaPan Jan 21 '16 at 15:08
  • 1
    \$\begingroup\$ Instead of Map, you can use TreeMap or TreeSet, which have unique values in sorted order, so you need not sort your array and worry about duplicate values. \$\endgroup\$ – Anjani Mittal Sep 10 '16 at 20:07
2
\$\begingroup\$

To avoid the duplicates, you need to make the decision whether that element is already part of the subset. To do so, you need to do search in the already considered elements for the subset.

The challenge is performing this search optimally. Available options are to use a BST to store the subset elements which can be summed to the target sum. The searching operation will be efficient (log2H H -height of tree). This operation needs to be performed for every element, so it's better to use a BST.

Another alternative is to sort the given input, which is at the cost of \$\mathcal{O}(n \log n)\$. Then we can easily check the duplicates in the subset as they are appearing consecutively.

Let's compare the above approach:

BST has two costs:

  1. Construction of BST for each subset and balancing it
  2. Cearching (log2H)

Sorting approach needs: \$\mathcal{O}(n \log n)\$

The winning answer is to maintain the HashSet of the subset and contains can be performed in \$\mathcal{O}(1)\$ constant time.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.