nmr_guy
BAN USERIf we were to assume that the array contains only positive numbers then there is some potential for cutting down on computation time, especially for large k. If using recursion, one would start from a set including all elements of the array, and then keep removing elements until the sum falls below k. At that point recursive branch is cut, which is what cuts down on the total number of function calls. Something like this:
static int K = 12;
static Integer [] array = { 1, 2, 3, 4, 5 };
static HashSet<String> resultsSet = new HashSet<String>();
private static void GenerateSubsets(ArrayList<Integer> list, int curSum) {
if(curSum < K) return; // We fell below K for the sum of all the elements in this list - return
resultsSet.add(list.toString());
for(int i=0; i < list.size(); i++) {
int curElem = list.get(i);
list.remove(i);
GenerateSubsets(list, curSum - curElem);
list.add(i, curElem);
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
int overallSum = 0;
for(int i: array) overallSum += i;
GenerateSubsets(list, overallSum);
}
Here is a more universal approach than described by Apostle, i.e. it doesn't assume that the square's sides are parallel to the axes. The complexity looks to be O(N^2).
1) For quick check-up on the existence of points with given coordinates, store all points in HashMap<String, int>. Here point coordinates are turned into String key as x+","+y.
2) Iterate i from 0 to N-1 and j from i+1 to N, where N is the total number of points. For each pair of points it is easy to predict where to expect the other corners of the square. You basically calculate the vector perpendicular to the line between your current two points. This vector is (ax, ay) = (y2-y1, -(x2-x1)), where (x1, y1) is the i-th point and (x2, y2) is the j-th point. The predicted positions will be either (x1+ax, y1+ay) & (x2+ax, y2+ay) OR (x1-ax, y1-ay) & (x2-ax, y2-ay).
3) If each point of the predicted pair exists in the HashMap then you found a square! I kept track of the found squares using an ArrayList<String>, because you find the same squares with different sequence of corners multiple times. In this ArrayList I represented as a sorted sequence of point indexes, turned into a string.
Notes: a) It might be enough to consider only predicted points (x1+ax, y1+ay) & (x2+ax, y2+ay). It yielded the same results on my test set of points. However, I am not good enough to prove that it will generally work :)
b) I was working with ints for my point coordinates, which actually limits you a lot on what kind of square orientations you can have. Ideally you'd want to switch to floats. However, due to the large number of significant digits that you would typically end up with, you wouldn't be able to get the HashMap to work. So I think for it to work you'd need to round coordinates to a fixed number of decimal places before you put them into HashMap. And then you just have to hope that you have enough precision to detect all the squares :)
Hi aka,
I like your code but I'm afraid you are breaking out of the recursion too early when you do "return" in the "if(target <= 0)" condition. You can easily see it if you use int a[] = {5, 4, 3, 2, 1}, and k=11 for example. This snippet here works better:
- nmr_guy August 11, 2013