|
|
Given number 1,2,3,4,5,6,7,8,9 find all sets that sums up to 10.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
74. Given number 1,2,3,4,5,6,7,8,9 find all sets that sums up to 10.....
Question:
Given number 1,2,3,4,5,6,7,8,9 find all sets that sums up to 10
eg. [1,9] [1,2,7],[1,2,3,4] find all possible set can be made.
maybe an answer1:
public static void generatesets(int sum,ArrayList<Integer> used,ArrayList left,int count){
if(count == left.size()-1){
return;}
if(sum == 10){
for(int i=0;i<=used.size()-1;i++)
System.out.print( used.get(i)+"");
System.out.print("\n");
return ;
}
if(sum > 10)return;
int temp = left.get(count);
sum = sum + temp;
used.add(temp);
generatesets(sum,used,left,count+1);
used.remove(new Integer(temp));
sum = sum-temp;
generatesets(sum,used,left,count+1);
}
maybe an answer2:
Dynamic programming can be used. Basically keep track of the difference in an auxiliary set that is less than 10. Then just output the sets in last index.
T(i) = set of all sets T(j) such that sum in T(j) <= 10 union set of all T(k) union T(i) that sums less than or equal to 10 AND difference of 10 with elements of T(k) union T(i) is either 0 or greater than Input[i]. This is because since we are processing array in sorted order, you won't find this number ever since we have already processed it!
Input Aux sets
1 {1}
2 {1}, {2}, {1,2}
3 {1}, {2}, {1,2}, {3}, {1,3}, {2, 3}
4 {1}, {2}, {1,2}, {3}, {1,3}, {2, 3}, {1,4}
5 {1}, {2}, {1,2}, {3}, {1,3}, {2, 3}, {1,4}, {2,3,5}, {1,4,5}
6 {1}, {2}, {1,2}, {3}, {1,3}, {2, 3}, {2,3,5}, {6,1,3}, {1,4,5}
7 {1}, {2}, {1,2,7}, {3,7}, {2,3,5}, {6,1,3}, {1,4,5}
8 {1}, {2,8}, {1,2,7}, {3,7}, {2,3,5}, {6,1,3}, {1,4,5}
9 {1,9}, {2,8}, {1,2,7}, {3,7}, {2,3,5}, {6,1,3}, {1,4,5}
10 {1,9}, {2,8}, {1,2,7}, {3,7}, {2,3,5}, {6,1,3}, {1,4,5}
maybe an answer3:
Key observation: use dynamic programming. partition the problem to be multiple sub-problems.
There are two difficulties. First, the result is a two-dimentional integer array, and the size of the array is hard to know in advance. So we better use dynamic array. In Java, we can ArrayList. Second, the base cases in the recursive call is complicated. How to handle it properly is also a challenge. Below is the runnable Java code:
package misc;
import java.util.ArrayList;
public class sumToN {
public ArrayList<ArrayList> sumTo(int start, int end, int n) {
ArrayList<ArrayList> al = new ArrayList();
if (start == n) { //base case
ArrayList<Integer> ret = new ArrayList();
ret.add(n);
al.add(ret);
return al;
}
for (int i=start;i<=end;i++) {
int nextN = n-i;
if (nextN == 0) {
ArrayList<Integer> row = new ArrayList();
row.add(i);
al.add(row);
continue;
} else if (i+1 > nextN) {
continue;
}
ArrayList<ArrayList> r = sumTo(i+1,end,nextN);
if (r != null) {
for (int k=0;k<r.size();k++) {
ArrayList<Integer> row = r.get(k);
row.add(i);
al.add(row);
}
}
}
return al;
}
public static void main(String[] args) {
sumToN s = new sumToN();
ArrayList<ArrayList> ret = s.sumTo(1, 9, 10);
StringBuffer sb = new StringBuffer();
for (int i=0;i<ret.size();i++) {
ArrayList<Integer> row = ret.get(i);
for (int k=0;k<row.size();k++) {
sb.append(""+row.get(k)+",");
}
sb.append('\n');
}
System.out.print(sb.toString());
}
}
(Continued on next question...)
Other Interview Questions
|
