使用整数1或2填充固定大小的数组以形成总和X.

Question

假设我有一个固定大小的数组.我想用1或2填充数组,以便所有元素总和为X.

例:

• 所需金额= 12
• 数组大小= 7

可能的组合:

array( 1, 2, 2, 2, 1, 2, 2 ) // sums to 12

array( 1, 1, 2, 2, 2, 2, 2 ) // sums to 12

Answer 1

• 找到数组中2的数字,这个数字是:

  #2's = X - array_size
  

• 选择随机任意#2's元素(例如第一个元素),并赋予它们值2,其余元素将获得值1.

注:很容易看到,如果X < array_size还是X> 2*array_size没有解决问题的方法(显然上述算法会失败)