Apple Division CSES Problem Set Solution | CSES Problem Set Solution Apple division with code

 Apple Division CSES Problem Set Solution | CSES Problem Set Solution Apple division with code -

Apple Division CSES Problem Solution Easy Explanation. Apple division is problem is taken form cses introductory problem set.Let's Read Problem statement first.

Problem Statement-

• Time limit: 1.00 s
 
• Memory limit: 512 MB

There are n$n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer n$n$: the number of apples.

The next line has n$n$ integers p1,p2,…,pn$p_1,p_2,\dots ,p_n$: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints

• 1≤n≤20$1\le n\le 20$
  
• 1≤pi≤109$1\le p_i\le {10}^9$
  

Example

Input:
5
3 2 7 4 1

Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Join Telegram channel for code discussion- https://t.me/competitiveProgrammingDiscussion

Solution-

Apple division problem can be solved using recursion because contrain is  too small so in can be done by recursion.

First we generate all subsequence of weight and which subset-sum difference is minimum we will print that ans.

For generating one subset we will use recursion for every element of array we have two choices either take it or not to take it. 

let say the entire array sum is  S.

and one of Subsequence sum is x so the sum of another segment of the array will be S-x . so the difference of two subsets of array is 

 abs((totalsum-currsum) - currsum);

currsum denote the sum of one subsequence.

so we will make recursive call now and return minimum ans 

return min(findminans(arr,currsum+arr[i],totalsum,i-1),findminans(arr,currsum,totalsum,i-1));

Here is my Code-