回溯法专题

ゝ一世哀愁。 2023-07-25 05:26 151阅读 0赞

### 回溯法 ###

*  全排列问题
 *  N皇后问题

枚举，排列，组合问题都可以用回溯法来求解，它也是一个通用的求解问题的算法

# 全排列问题 #

比如给你数组1，2，3，输出该数组所有可能的全排列  
https://blog.csdn.net/u013568373/article/details/92800407  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]

> add: 1 add: 2 add: 3  
> remove: 3 remove: 2  
> add: 3 add: 2  
> remove: 2 remove: 3 remove: 1  
> add: 2 add: 1 add: 3  
> remove: 3 remove: 1  
> add: 3 add: 1  
> remove: 1 remove: 3 remove: 2  
> add: 3 add: 1 add: 2  
> remove: 2 remove: 1  
> add: 2 add: 1  
> remove: 1 remove: 2 remove: 3

class Solution { 
        List<Integer> tlist = new ArrayList<>();
        static List<List<Integer>> rsl = new ArrayList<>();
        static boolean[] used = null;
    
        public static void main(String[] args) { 
            Solution solution = new Solution();
            int[] ints = { 1, 2, 3};
            used = new boolean[ints.length];
            solution.generate(ints, 0);
            System.out.println(rsl);
        }
    
        public void generate(int[] nums, int treeLen) { 
    
            if (treeLen == nums.length) { 
                /** * 这里需要格外注意：不能写成rsl.add(tlist); * 否则rsl的结果是[[],[],[],[],[],[]] */
                rsl.add(new ArrayList<>(tlist));
                return;
            }
            for (int i = 0; i < nums.length; i++) { 
                if (!used[i]) { 
                    tlist.add(nums[i]);
                    used[i] = true;
                    generate(nums, treeLen + 1);
                    tlist.remove(tlist.size() - 1);
                    used[i] = false;
                }
            }
            return;
        }
    }

# N皇后问题 #

[origin link][]  
要求在一个n×n的棋盘上放置n个皇后，使得任意两个皇后不在同一行或同一列或同一斜线上。  
输出所有可能的n个皇后的坐标

public class Ab { 
        ArrayList<Location> locations = new ArrayList<>();
        static ArrayList<ArrayList> rst = new ArrayList<>();
    
        public static void main(String[] args) { 
            Ab ab = new Ab();
            ab.NQueen(4, 0);
            System.out.println(rst);
        }
    
        public void NQueen(int n, int y) { 
            if (y == n) { 
                rst.add(new ArrayList(locations));
                return;
            }
            for (int i = 0; i < n; i++) { 
                Location lct = new Location(i, y);
                if (isable(locations, lct)) { 
                    locations.add(lct);
                    NQueen(n, y + 1);
                    locations.remove(lct);
                }
            }
        }
    
        public boolean isable(List<Location> locations, Location lc) { 
            for (Location location : locations) { 
                if (lc.x == location.x || lc.y == location.y) { 
                    return false;
                } else if (Math.abs(location.x - lc.x) == Math.abs(location.y - lc.y)) { 
                    return false;
                }
            }
            return true;
        }
    
        class Location { 
            int x;
            int y;
    
            public Location(int x, int y) { 
                this.x = x;
                this.y = y;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]: /images/20230528/d105e94e09ae488da7ce4ec5c07e87e4.png
[origin link]: https://blog.csdn.net/qq_38046510/article/details/80055560