首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 46. Permutations

leetcode: 46. Permutations

作者头像
JNingWei
发布2018-09-27 17:13:31
3970
发布2018-09-27 17:13:31
举报
文章被收录于专栏:JNing的专栏JNing的专栏

Problem

# Given a collection of distinct numbers, return all possible permutations.
#
# For example,
# [1,2,3] have the following permutations:
# [
#     [1,2,3],
#     [1,3,2],
#     [2,1,3],
#     [2,3,1],
#     [3,1,2],
#     [3,2,1]
# ]

Idea

当只有1时候:[1]
当加入2以后:[2, 1], [1, 2]
当加入3以后:[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]
前3个permutation分别对应将3插入[2, 1]的0, 1, 2的位置。
同理后3个为插入[1, 2]的。因此可以用逐个插入数字来构造所有permutations。

AC

DFS:

class Solution():
    def permute(self, x):
        return self.dfs(x)
    def dfs(self, x):
        if len(x) == 0:
            return []
        if len(x) == 1:
            return [x]
        pre, cur = self.dfs(x[:-1]), []
        for p in pre:
            for i in range(len(x)):
                cur.append(p[:i] + [x[-1]] + p[i:])
        return cur


if __name__ == "__main__":
    assert Solution().permute([1, 2, 3]) == [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年11月16日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem
    • Idea
    • AC
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档