LintCode 896. PrimeProduct - Weekly9

http://www.lintcode.com/en/problem/prime-product/

it's a tricky question if you are trying to if-else for 2 to 9 for-loops.

but we can simply use the DFS search.

Then eliminate duplication, and apply ordering.

	public class Solution {
	/**
	* @param arr: The prime array
	* @return: Return the array of all of prime product
	*/
	int[] getPrimeProduct(int[] A) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return new int[0];
	}
	this.A = A;
	this.set = new HashSet<>();
	helper(0, 1, 0);
	TreeSet<Integer> treeSet = new TreeSet<>(set);
	int[] answer = new int[treeSet.size()];
	for (int i = 0; i < answer.length; i++) {
	answer[i] = treeSet.pollFirst();
	}
	// return the final result
	return answer;
	}
	private void helper(int index, int product, int counter) {
	if (index == A.length) {
	if (counter > 1) {
	set.add(product);
	}
	} else {
	helper(index + 1, product * A[index], counter + 1);
	helper(index + 1, product, counter);
	}
	}
	int[] A;
	HashSet<Integer> set;
	}

view raw LintCode No896_PrimeProduct - Weekly9 - LintCode.java hosted with ❤ by GitHub