## Computer Science & Engineering Problem Solving Lab Experiments

# Recursion

Welcome to recursion. One of the most easiest things to code but really hard to debug! Recursion is a very powerful tool to solve problems. All loops(while, for , do while) can be simulated using recursion. Also the main step of the dynamic programming is recursion which is useful in solving many algorithmically difficult problems. Lets solve some problems now.

## Problem 1:

You are given scales for weighing loads. On the left side lies a single stone of known weight W < 2N. You own a set of N different weights, weighing 1, 2, 4, ..., 2^{N}−1 units of mass respectively. Determine how many possible ways there are of placing some weights on the sides of the scales, so as to balance them (put them in a state of equilibrium).

**Input Specification**

The input line contains two integers: N W, where N denotes the number of weights and W represents the weight to be placed on the left side.

**Output Specification**

Output must be a single integer denoting the number ways in which one can balance the weight W by placing weights on any side.

**Sample Input and Output**

Input: 2 4

Output: 3

Input: 5 10

Output: 14

## Problem 2:

Given a weighing pan, n weights and a destination weight D, print “YES” or “NO” depending whether you can weight D using other weights given.

**Input Specification**

Input begins with numbers of weights n, then n values denoting mass of each weight and then in the end destination weight D.

**Output Specification**

As the output, print “YES” if it is possible to weight D, otherwise “NO”.

**Sample Input and Output**

Input: 3 1 3 4 2

Output: YES

Input: 2 1 3 5

Output: NO