有一組數(shù)字[0,1,2,3,4,5,6,7,8,9],現(xiàn)給出一個數(shù)字，比如3，要求從該組數(shù)字中選出相加等于3的組合（相加的數(shù)字3個），如0+0+3=3，0+1+2，3個相加的數(shù)字不能相同（如1+1+1就不行），無順序要求。大概函數(shù)是這樣 fun(數(shù)組,和值,3) ,得到的是組合的個數(shù).參數(shù)3是相加的數(shù)字個數(shù)，這里規(guī)定是3，如0+0+3，這是3個數(shù)字
3 回答
幕布斯6054654
TA貢獻1876條經(jīng)驗 獲得超7個贊
遞歸查找符合規(guī)則的元素集合：
部分邏輯是建立在認為集合中所有元素都是正數(shù)的基礎(chǔ)上
(() => {
var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(calc(arr, 3, 3)) // 0,1,2
console.log(calc(arr, 3, 1)) // 3
function calc (arr, total, count, feed = []) {
if (count === 1) { // check
return arr.includes(total) ? feed.concat(total) : null
} else if (count > 1) { // remove big number
arr = arr.filter(item => item < total)
} else if (count === 0) { // maybe too large
return total === 0 ? feed : null
} else if (total < 0 || count < 0) { // too large
return null
}
for (let [index, item] of Object.entries(arr)) {
let result = calc([
...arr.slice(0, index),
...arr.slice(index + 1)
], total - item, count - 1, feed.concat(item))
if (result) return result
}
return null
}
})()
冉冉說
TA貢獻1877條經(jīng)驗 獲得超1個贊
請參考以下 python 代碼實現(xiàn)
# -*- coding: utf-8 -*-
"""
author: 李毅
"""
from unittest import TestCase
def permutation(array, nsum):
''' 假設(shè)數(shù)組元素不重復(fù)。 '''
# 排序（升序）
sarray = sorted(array)
# 找出最大下標
max_idx = len(sarray)
for i, e in enumerate(sarray):
if e > nsum:
max_idx = i
break
# 窮舉
result = []
for i in range(max_idx):
for j in range(i, max_idx):
for k in range(j, max_idx):
if i == j and j == k:
continue
if sarray[i] + sarray[j] + sarray[k] == nsum:
result.append((sarray[i], sarray[j], sarray[k]))
return result
class Test(TestCase):
""" 單元測試 """
def test_permutation(self):
self.assertEqual(
permutation(range(10), 3),
[(0, 0, 3), (0, 1, 2)])
self.assertEqual(
permutation(range(10), 2),
[(0, 0, 2), (0, 1, 1)])
# 邊界值
self.assertEqual(
permutation(range(3), 3),
[(0, 1, 2)])
self.assertEqual(
permutation(range(1, 4), 4),
[(1, 1, 2)])添加回答
舉報
0/150
提交
取消