Return the change

Given set of coins find the minimum number of coins required to return sum 'S'.
Let available set of coins be represented by array Coins. If sum can not be returned print -1
Assuming coins array is sorted.

Solution: O(N^2) where N is number of coins.

Sum[i] = min { Sum[i-Coin[j]] }  + 1, Sum[i-Coin[j]] != -1 && Coin[j] < i
if for all Sum[i-Coin[j]] == -1, Sum[i] = -1;

Test case

Coins: 1 3 4 5
Sum: 7
Min coin: 2

Sum:9
Min coin:2

Coins: 2 5 8 19
Sum:1
Min coin -1

Sum: 24
Min coin:2

Sum:23
Min coin: -1

Working code

 #include <stdio.h>  
  #include <iostream>  
  #define max(a,b) a>b?a:b  
  using namespace std;  
  int main() {  
  int n;  
  cin>>n;  
  int coin[n];  
  for(int i=0;i<n;i++) {  
  cin>>coin[i];  
  }  
  int s;  
  cin>>s;  
  int found = 0,min;  
  int sum[s+1];  
  sum[0] = 0;  
  for(int i=1;i<=s;i++) {  
  found = 0;  
  min = i;  
  for(int j=0;j<n && coin[j] <= i;j++) {  
   if(sum[i-coin[j]] != -1) {  
   found = 1;  
   if(sum[i-coin[j]] < min) {  
   min = sum[i-coin[j]];  
   }  
   }  
  }  
  if(!found) {  
   sum[i] = -1;  
  } else {  
   sum[i] = min + 1;  
  }  
  }  
  cout<<sum[s]<<endl;  
  return 0;  
  }