CareerCup

we can use a DP here
for all numbers from i=1 to n.
Therefore time complexity O(n2)

(Not sure about the minimum subset in question it looks to be a minimum of 2)
Rest part is simple

// changing the functionality of pair
static int ways_sum =o;
static int min_counter =0;

void Pair(int a[], int size_array,int sum)
{
Loop ( i=0;a[] <size_array; i++)
{
Loop(j=1;j<array-size;j++)
{
Loop(k=j;k<array_size;k++)
{
ways_sum =a[i] + a[k];
if ( ways_sum == SUM)
{
min_counter++;
break;
}
}
}

}

This is nothing but variation of subsetsum problem which can be solved using dynamic programming:

geeksforgeeks.org/dynamic-programming-subset-sum-problem/

Subset Sum Problem. DP is the best approach and uses n2 run time

I'm not seeing how DP helps.

int ways(int [] array, int target, int start, int setSize)
	{
		int count = 0;
		if (setSize == 1)
		{
			for (int i=start; i<array.length; ++i)
			{
				if (target == array[i])
				{
					++count;
				}
			}
		}
		else
		{
			for (int i=start; i<array.length; ++i)
			{
				if (target >= array[i])
				{
					count += ways(array, target - array[i], i, setSize - 1);
				}
			}
		}
		return count;
	}
	
	int minimumSubset(int [] array, int target)
	{
		System.out.println("Target = " + target + ", array = " + Arrays.toString(array));
		int s;
		int count = 0;
		for (s=1; s<=array.length; ++s)
		{
			count = ways(array, target, 0, s);
			if (count > 0)
			{
				break;
			}
		}
		System.out.println("s = " + s + ", ways = " + count);
		return 0;
	}

It is a DP problem, modified version of coin change problem..

try this.sort the array first and then go from last .check whether last element is smaller than number.If yes then get the remainder.Have a binary search of it and then take the largest of all numbers which are smaller than the remainder.continue this.Please correct me if I am wrong.

It is a np complete subset problem and hence can be done by backtracking

in the given question if i take example number 3
the output should be 2 2 ({7,7} and {1,1,1,1,1,1,1}) as there is no restriction in how many times we can use the given number ?? please comment if you think i am wrong

sry i interpretate wrong logic.