TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超9個(gè)贊
遞歸查找符合規(guī)則的元素集合：
部分邏輯是建立在認(rèn)為集合中所有元素都是正數(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貢獻(xiàn)1794條經(jīng)驗(yàn) 獲得超8個(gè)贊
請參考以下 python 代碼實(shí)現(xiàn)
# -*- coding: utf-8 -*-
"""
author: 李毅
"""
from unittest import TestCase
def permutation(array, nsum):
''' 假設(shè)數(shù)組元素不重復(fù)。 '''
# 排序（升序）
sarray = sorted(array)
# 找出最大下標(biāo)
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)])
舉報(bào)