-
Notifications
You must be signed in to change notification settings - Fork 0
/
SubSet.java
130 lines (99 loc) · 2.29 KB
/
SubSet.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*
Sum of Subsets
==============
Example Output:
==============
Enter no of elements
5
Enter elements
1 2 3 5 6
Enter the requried sum :
10
Solution
1
3
6
Solution
2
3
5
=======================
Enter no of elements
3
Enter elements
10 20 30
Enter the requried sum :
25
NO SOLUTION
=======================
Enter no of elements
3
Enter elements
20 42 56
Enter the requried sum :
15
NO SOLUTION
======================
*/
import java.io.*;
import java.util.*;
class SubSet
{
static int c;
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
//Input no of elements
System.out.println("Enter no of elements ");
int n=s.nextInt();
//Init sum to 0
int sum=0;
//Input the elements and calculate the sum of them
System.out.println("Enter elements ");
int w[]=new int[n];
for(int i=0;i<n;i++)
{ w[i]=s.nextInt();
sum+=w[i];
}
int x[]=new int[n];
//Input requried sum
System.out.println("Enter the requried sum : ");
int d= s.nextInt();
//count var
c=0;
//calculation of sum,already done in above input loop
//Check if sum is smaller than the requried sum or if the first element itself is greater than the sum
if(sum<d || w[0]>d)
System.out.println("NO SOLUTION");//then no possible sol exists
else //Else call the function
subset(0,0,sum,x,w,d);
if(c==n-1)//if there is no solution even after all reursions
System.out.println("NO SOLUTION");
}
static void subset(int cs,int k,int r,int x[],int w[],int d)
{
x[k]=1;//Pick k'th element
c++;
//If current sum + next element = requried solution we Print out the w[i] for which x[i]=1;
if(cs + w[k]==d)
{
System.out.println("Solution");
for(int i=0;i<=k;i++)
{
if(x[i]==1)
System.out.println(w[i]);
}
}
//If current sum + next-next(k+1)'th element is less than requried sum then we include the next element(k) and recurse with k+1
else if(cs+w[k]+w[k+1]<=d)
{
subset(cs+w[k],k+1,r-w[k],x,w,d);
}
//If including next element(k) from remaining excedes req sum but the next-next(k+1)th element can be included not to exceed req sum
if(cs+r-w[k]>=d && cs+w[k+1]<=d)
{
x[k]=0;//Then exculde the selected , next element(k)
subset(cs,k+1,r-w[k],x,w,d);//recurse without adding w[k] to cs
}
}
}