2022-10-21：你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。 你要用 所有的火柴棍 拼成一个正方形。 你 不能折断 任何一根火柴

2022-10-21：你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。
你要用 所有的火柴棍 拼成一个正方形。
你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能拼出正方形，则返回 true ，否则返回 false 。
输入: matchsticks = [1,1,2,2,2]。
输出: true。

答案2022-10-21：

状态压缩的动态规划。
力扣473。各种语言测试，rust运行速度最快，内存占用最低，golang次之，java和c#最慢并且内存占用最高。

代码用rust编写。代码如下：

use std::iter::repeat;

impl Solution {

    pub fn makesquare(matchsticks: Vec<i32>) -> bool {

        let mut matchsticks = matchsticks;

        let mut sum = 0;

        for num in matchsticks.iter() {

            sum += num;

        }

        if sum & 3 != 0 {

            return false;

        }

        let mut dp: Vec<i32> = repeat(0).take(1 << matchsticks.len()).collect();

        return Solution::process(&mut matchsticks, 0, 0, sum >> 2, 4, &mut dp);

    }

    fn process(

        arr: &mut Vec<i32>,

        status: i32,

        cur: i32,

        len: i32,

        edges: i32,

        dp: &mut Vec<i32>,

    ) -> bool {

        if dp[status as usize] != 0 {

            return dp[status as usize] == 1;

        }

        let mut ans = false;

        if edges == 0 {

            ans = if status == (1 << arr.len()) - 1 {

                true

            } else {

                false

            };

        } else {

            let mut i = 0;

            while i < arr.len() as i32 && !ans {

                if ((1 << i) & status) == 0 && cur + arr[i as usize] <= len {

                    if cur + arr[i as usize] == len {

                        ans |= Solution::process(arr, status | (1 << i), 0, len, edges - 1, dp);

                    } else {

                        ans |= Solution::process(

                            arr,

                            status | (1 << i),

                            cur + arr[i as usize],

                            len,

                            edges,

                            dp,

                        );

                    }

                }

                i += 1;

            }

        }

        dp[status as usize] = if ans { 1 } else { -1 };

        return ans;

    }

}

fn main() {

    let matchsticks = vec![1, 1, 2, 2, 2];

    let ans = Solution::makesquare(matchsticks);

    println!("ans = {:?}", ans);

}

struct Solution {}

执行结果如下：

左神java代码

2022-10-21：你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。 你要用 所有的火柴棍 拼成一个正方形。 你 不能折断 任何一根火柴的相关教程结束。