Interview Question
Country: United States
+1, even if this problem talks about enumerating all sets. Sethi's divide and conquer algorithm for subset sum can be used here, though.
In an interview, I believe all the interviewer want to see is if can write a simple recursive method...
@Loler, I've searched for "Sethi's divide and conquer algorithm", but I couldn't find anything. Typo?
void SubSets(int s, int k ,int r)
{
if( s + m_arr[k] == target )
{
choose[k] = 1;
for(int j= 0; j < 5 ; j++)
{
if( choose[j] == 1)
{
cout<<" ";
cout<<m_arr[j];
}
}
for(int j= 0; j < 5 ; j++)
{
choose[j] = 0;
}
cout<<endl;
}
else if ( (s + m_arr[k] + m_arr[k+1]) <= target)
{
choose[k] = 1;
SubSets(s+m_arr[k] , k+1, r-m_arr[k]);
}
if(((s + r + -m_arr[k]) >= target) && ( (s + m_arr[k+1]) <= target))
{
choose[k] = 0;
SubSets(s ,k+1, r-m_arr[k]);
}
}
public class FindSquare {
public boolean isSquare(int value)
{
int sum = 0;
int odd = 1;
boolean result = false;
while(value > sum)
{
sum = sum + odd;
odd = odd + 2;
}
System.out.println(sum);
if(sum == value)
{
result = true;
}
return result;
}
public static void main(String[] args)
{
System.out.println(new FindSquare().isSquare(16));
}
}
You can solve it like:
a.First sort the array in non-decreasing order.Take two pointers left and right.Left point to the start and the right pointer points to the end of the array.
b.while(left<right)
b.check whether a[left]+a[right]<k.If yes then increment the left pointer by one.
c.check whether a[left]+a[right]>k.If yes decrement the right pointer by one.
d.If a[left]+a[right]==k.Return true.
subset sum problem.Google it up.
- aka June 12, 2013