例如，如果硬币= [1，2,5]和N = 11，返回真，如果硬币= [3，77]和N = 100，则返回

Question

线上等待。〜

给定数量的硬币以不同的面额，例如[1,2,5]，并测试它们是否可以用来弥补一定的金额（N），假设您可以在每个面额中使用无限数量的硬币。例如，如果硬币= [1，2,5]和N = 11，返回真，如果硬币= [3，77]和N = 100，则返回

Answer 1

的想法是使用一个递归函数（在这里它会计算用一枚第一枚硬币与其他一批硬币递归地缩小硬币阵列的大小）。

但SR我不熟悉Objective-C的，所以我写一个使用C＃。使用应将其转换为Objective-C。

bool CanDo(int n, int [] arr) 
{ 
    if (arr.Length == 1) 
    { 
     if (n % arr[0] == 0) 
     { 
      return true; 
     } 
    } 
    else 
    { 
     var ls = new List<int>(arr); 
     ls.RemoveAt(0); 
     int [] newarr = ls.ToArray(); //Create New array by deleting first element(current calculated element) of old array 

     for(int i = 0; i <= n/arr[0]; i++) 
     { 
      int next_n = n - i * arr[0]; 
      if (next_n == 0) 
      { 
       return true; 
      } 
      else if (next_n < 0) 
      { 
       break; 
      } 
      else if(next_n > 0) 
      { 
       if(CanDo(next_n, newarr)) 
       { 
        return true; 
       } 
      } 
     } 
    } 
    return false; 
} 

这是在C＃中完整的代码，可以打印到控制台首次发现的解决方案。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static List<string> resultString = new List<string>(); 
     static bool CanDo(int n, int [] arr) 
     { 
      if (arr.Length == 1) 
      { 
       if (n % arr[0] == 0) 
       { 
        resultString.Add(n/ arr[0] + "*" + arr[0]); 
        return true; 
       } 
      } 
      else 
      { 
       var ls = new List<int>(arr); 
       ls.RemoveAt(0); 
       int [] newarr = ls.ToArray(); //Create New array by deleting first element of old array 

       for(int i = 0; i <= n/arr[0]; i++) 
       { 
        if (resultString.Count > 0) 
        { 
         resultString.RemoveAt(resultString.Count - 1); 
        } 

        int next_n = n - i * arr[0]; 
        if (next_n == 0) 
        { 
         resultString.Add(i + "*" + arr[0]); 
         return true; 
        } 
        else if (next_n < 0) 
        { 
         break; 
        } 
        else if(next_n > 0) 
        { 
         if (i != 0) 
         { 
          resultString.Add(i + "*" + arr[0] + " + "); 
         } 
         if(CanDo(next_n, newarr)) 
         { 
          return true; 
         } 
        } 
       } 
      } 
      return false; 
     } 
     static void Main(string[] args) 
     { 
      try 
      { 

       int[] arr = { 3, 5, 7 }; 
       int N = 20; 
       resultString = new List<string>(); 

       if (CanDo(N, arr)) 
       { 
        resultString.ForEach(Console.WriteLine); 
        Console.Read(); 
       } 
       else 
       { 
        Console.Write("Can't do"); 
        Console.Read(); 
       } 

      } 
      catch (Exception ex) 
      { 
       //handle exception 
      } 

     } 
    } 
}