求和

[编程题]求和

热度指数：21129 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来

输入描述:

每个测试输入包含2个整数,n和m

输出描述:

按每个组合的字典序排列输出,每行输出一种组合

示例1

输入

5 5

输出

1 4<br/>2 3<br/>5

算法知识视频讲解

Python

NewP

n,m = map(int,input().split())
res = []

def f(n, m, res, k):
    if m == 0:
        print(' '.join(res))
    for i in range(k, n+1):
        if i > m:
            break
        res.append(str(i))
        f(n, m-i, res, i+1)
        res.pop()

f(n, m, res, 1)

编辑于 2018-09-11 14:46:51 回复(0)

Python

离疏

#深度优先遍历
def rec(i, m, res):
    ans = []
    for j in range(i, n+1):
        if j == m:
            ans.extend([x+[j] for x in res])
            break
        if j < m:
            ans.extend(rec(j+1, m-j, [x+[j] for x in res]))
        else:
            continue
    return ans

n,m=list(map(int,input().split()))
ans = rec(1, m, [[]])
for a in ans:
    print(' '.join([str(x) for x in a]))

发表于 2018-06-28 11:26:49 回复(0)

Python

Yrichhhh

import traceback
# 回溯法
def backtracing(t, temp, sum, n, m):
    if (sum == m):
        print(" ".join(map(str, temp)))
    else:
        for i in range(t + 1, n + 1):
            if i + sum <= m:
                temp.append(i)
                backtracing(i, temp, sum + i, n, m)
                temp.pop()
try:
    n, m = input().strip().split()
    n = int(n)
    m = int(m)
    backtracing(0, [], 0, n, m)
except:
    traceback.print_exc()

发表于 2018-06-22 15:12:51 回复(0)

Python

新鲜菜鸡🐔

DP保存路径。

n,m = map(int,input().split())
ans =  [[None for i in range(n+1)] for j in range(m+1)]
for i in range(n+1):
    ans[0][i] = [[]]
for i in range(1,m+1):
    for j in range(1,n+1):
        if i-j<0:
            ans[i][j] = ans[i][j-1]
        else:
            if ans[i-j][j-1]==None:
                ans[i][j] = ans[i][j - 1]
            elif ans[i][j - 1]==None:
                ans[i][j] = [x+[j] for x in ans[i-j][j-1]]
            else:
                ans[i][j] = ans[i][j-1]+[x+[j] for x in ans[i-j][j-1]]
ans = ans[-1][-1]
for line in sorted([' '.join(map(str,x)) for x in ans]):
    print(line)

编辑于 2018-05-24 01:09:02 回复(0)

Python

小欣8

def rec(i, m, res):
    ans = []
    for j in range(i, n+1):
        if j == m:
            ans.extend([x+[j] for x in res])
            break
        if j < m:
            ans.extend(rec(j+1, m-j, [x+[j] for x in res]))
        else:
            continue
    return ans


if __name__ == '__main__':
    n, m = [int(x) for x in input().split()]
    ans = rec(1, m, [[]])
    for a in ans:
        print(' '.join([str(x) for x in a]))

编辑于 2017-10-01 20:21:36 回复(4)