个人中心
gpt4 book ai didi

algorithm - 如何使用回溯生成给定元素数组的所有组合？

转载 作者：塔克拉玛干 更新时间：2023-11-03 06:06:03 24 4
gpt4 key购买 nike

<分区>

给定一个数组，生成所有组合

例如:

输入:{1,2,3}

输出:{1}、{2}、{3}、{1,2}、{2,1}、{1,3}、{3,1}、{2,3}、{3、 2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

我正在练习回溯算法，我想我了解回溯的一般概念。您实质上是在运行 DFS 来查找满足条件的路径。如果你命中一个不满足条件的节点，退出当前节点并从前一个节点开始。

但是，我无法理解如何实现隐式树的遍历部分。

我最初的想法是沿着最左边的路径遍历，这将给我 {1}、{1,2}、{1,2,3}。但是，一旦我回溯到 1，我如何继续添加 3 以获得 {1,3} 和 {1,3,2} 之后？即使我有 2 个指针，我也需要它指向 2 才能最终获得 {1,3,2}。

我应该采取什么步骤来解决像这样的回溯问题？

enter image description here

感谢大家的回复。这是我想出的算法。

    public static void main(String[] args){
    char[] arr = {'1', '2', '3'};

    List<List<Character>> ans = new ArrayList<>();

    List<Character> combination = new ArrayList<>(3);

    Queue<Character> queue = new LinkedList<>();

    for(Character ch : arr){
        queue.add(ch);
    }

    Combination comb = new Combination();

    comb.solve(0, arr, queue, combination, ans);

    print(ans);
}


    public void solve(int index, char[] arr, Queue<Character> queue,  List<Character> combination, List<List<Character>> ans){
    if(index == arr.length){
        return;
    }else{
        for(int i=index;i<arr.length;i++){
            // Choose
            char next = queue.poll();   
            combination.add(next);
            ans.add(new ArrayList(combination));

            // Explore
            solve(index+1, arr, queue, new ArrayList(combination), ans);

            // Unchoose
            combination.remove(combination.size()-1);
            queue.add(next);
        }
    }
}

Output
1, 
1, 2, 
1, 2, 3, 
1, 3, 
1, 3, 2, 
2, 
2, 3, 
2, 3, 1, 
2, 1, 
2, 1, 3, 
3, 
3, 1, 
3, 1, 2, 
3, 2, 
3, 2, 1,

24 4 0
文章推荐： php - 使用 PHP 的透明圆形裁剪图像
文章推荐： python - 具有工作时间上下文的日期时间列表，计算非工作时间
文章推荐： php - 从PHP中的文档根目录中减去路径
文章推荐： PHPUnit 找不到 PHPUnit_Extensions_Story_TestCase。缺少什么包裹？
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com