Interview Question
Country: United States
import java.util.Scanner;
import java.util.Stack;
public class GetAllSubsetByStack {
/** Set a value for target sum */
public static final int TARGET_SUM = 10;
private Stack<Integer> stack = new Stack<Integer>();
/** Store the sum of current elements stored in stack */
private int sumInStack = 0;
public void populateSubset(int[] data, int fromIndex, int endIndex) {
System.out.println("Recursion Called");
/*
* Check if sum of elements stored in Stack is equal to the expected
* target sum.
*
* If so, call print method to print the candidate satisfied result.
*/
if (sumInStack == TARGET_SUM) {
print(stack);
}
for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
System.out.println("Processing "+data[currentIndex]);
if (sumInStack + data[currentIndex] <= TARGET_SUM) {
stack.push(data[currentIndex]);
System.out.println("Element"+data[currentIndex]+"Pushed");
sumInStack += data[currentIndex];
System.out.println("sumInStack1:"+sumInStack);
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
sumInStack -= (Integer) stack.pop();
System.out.println("sumInStack2:"+sumInStack);
}
}
}
/**
* Print satisfied result. i.e. 15 = 4+6+5
*/
private void print(Stack<Integer> stack) {
StringBuilder sb = new StringBuilder();
sb.append(TARGET_SUM).append(" = ");
for (Integer i : stack) {
sb.append(i).append("+");
}
System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
}
private static final int[] DATA = { 1, 3, 5,2,7};
public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}
/**
* find all subset which have summation = certain value in list
*
* @author mohamed
*
*/
public class SubSetSum {
// list of numbers
private static int[] list = { 1, 3, 5, 2, 7 };
/**
*
* @param index
* index = 0
* @param rem
* = K (the value which sum of subset must be)
* @param visited
* bitmask equal list in length and all items in it= "false"
* @return true if subset found else false
*/
private static boolean get(int index, int rem, boolean[] visited) {
// base case
if (index == list.length || rem < 0)
return false;
if (rem == 0) {
// if we find subset its sum = rem
for (int i = 0; i < visited.length; i++) {
if (visited[i])
System.out.print(list[i] + " ");
}
System.out.println();
return true;
} else {
visited[index] = true;
boolean res1 = get(index + 1, rem - list[index], visited);
visited[index] = false;
return res1 | get(index + 1, rem, visited);
}
}
public static void main(String[] args) {
get(0, 10, new boolean[list.length]);
}
}
There are multiple combinations by which a subset can be formed with sum equal to given sum. Hence, this problem is exponential.
Now, think of it this way : We start from first number (1 in given example), and combine it with remaining elements on right side of this number (3, 5, 2, 7), i.e, {1, 3}, {1, 5}, {1, 2}, {1, 7}. Now, we check if the sum of this set is equal to given sum. If yes, then add that set to solution set.
If not then just return an empty set. Do the above recursively, hence, in next iteration, we will have {1, 3, 5}, {1, 5, 2}, {1, 2, 7} - among these {1, 2, 7} is equal to given sum, hence this will be added to solution set. Again in next iteration, {1, 3, 5, 2} (> 10), {1, 5, 2, 7} (> 10) will be discarded as they are greater than given sum.
The above process is only for number 1. Then move onto next numbers 3, 5, 2 and 7 and repeat the above recursively.
#include <iostream>
#include <deque>
namespace
{
typedef std::deque<int> array;
typedef std::deque<int> set;
typedef std::deque<std::deque<int>> subsets;
}
class subsets_equal_sum
{
public :
std::deque<std::deque<int>> operator()(const std::deque<int>& a, const int& s)
{
if(a.empty()) return std::deque<std::deque<int>>();
return find_subsets_equal_sum(a, s, std::deque<int>(), 0);
}
std::deque<std::deque<int>> find_subsets_equal_sum(const std::deque<int> a, int s, std::deque<int> ps, size_t start)
{
if(s == 0)
{
subsets t;
t.push_back(ps);
return t;
}
if(s < 0) return std::deque<std::deque<int>>();
if(start == a.size()) return std::deque<std::deque<int>>();
subsets ss;
for(; start < a.size(); ++start)
{
set sp(ps.begin(), ps.end());
sp.push_back(a[start]);
subsets sst(find_subsets_equal_sum(a, s - a[start], sp, start + 1));
ss.insert(ss.end(), sst.begin(), sst.end());
}
return ss;
}
};
int main()
{
array a{1, 3, 5, 2, 7};
subsets_equal_sum ses;
std::cout << "\n[";
subsets ss(ses(a, 10));
for(size_t ssi(0); ssi < ss.size(); ++ssi)
{
std::cout << "{";
for(size_t si(0); si < ss[ssi].size(); ++si) std::cout << ss[ssi][si] << ((si == (ss[ssi].size() - 1)) ? "" : ", ");
std::cout << ((ssi == (ss.size() - 1)) ? "}" : "}, ");
}
std::cout << "]";
return 0;
}
- Satveer Singh Mechu June 02, 2014// CareerCup:- find subsets in array whose sum equal to a given number?? //example: S={1,3,5,2,7} and k=10, answer is {1,2,7},{3,5,2},{3,7} #include<iostream> using namespace std; void PrintPairs(int **p,int k, int i, int arr[]) { if(i <= 0 || k == 0) return; if(p[k][i] == 1) { int x = arr[i-1]; if(k >= x && p[k-x][i-1] == 1) { cout<<x<<" "; k = k - x; i = i-1; } else { i = i -1; } PrintPairs(p,k,i,arr); } } void SubSetSumK(int arr[], int n, int k) { int **p = new int*[k+1]; for(int i = 0; i <= k; i++) { p[i] = new int[n+1]; } for(int i = 0; i <= k; i++) { for(int j = 0; j <= n; j++) { p[i][j] = 0; } } for(int i = 0; i <= n; i++) { p[0][i] = 1; } for(int i = 1; i <= k; i++) { p[i][0] = 0; } for(int i = 1; i <= k; i++) { for(int j = 1; j <= n; j++) { p[i][j] = p[i][j-1]; //if we not use curr element //curr element value int x = arr[j-1]; if(i >= x) { p[i][j] = p[i][j] | p[i-x][j-1]; } //cout<<p[i][j]<<" "; } //cout<<endl; } cout<<"\nPrinting SubSet With Sum="<<k<<endl; for(int i = 1; i <= n; i++) { if(p[k][i] == 1) { PrintPairs(p,k,i,arr); cout<<endl; } } for(int i = 0; i <= n; i++) { delete [] p[i]; } delete [] p; } int main() { int arr[] = {5,2,3,4,1,6}; SubSetSumK(arr,6,11);//Sum = 11 } Output:- Printing SubSet With Sum=11 4 2 5 1 3 2 5 6 1 4