Snapchat - ColorSum

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_colorsum.html

给一些RGB的点，比如(86, 5, 211), (128, 99, 5), 再一个target点，看使用这些给的点能不能叠加得到target，每个点只能用一次

就是最基本的backtracking

public class ColorSum {
    static class Color {
        int r;
        int g;
        int b;
        public Color(int r, int g, int b) {
            this.r = r;
            this.g = g;
            this.b = b;
        }

        public void add(Color color) {
            this.r = (this.r + color.r > 255)? 255: (this.r + color.r);
            this.g = (this.g + color.g > 255)? 255: (this.g + color.g);
            this.b = (this.b + color.b > 255)? 255: (this.b + color.b);
        }

        public boolean substract(Color color) {
            if(color.r > this.r || color.g > this.g || color.b > this.b) {
                return false;
            }
            this.r = this.r - color.r;
            this.g = this.g - color.g;
            this.b = this.b - color.b;
            return true;
        }

        public boolean equalsZero() {
            return r == 0 && g == 0 && b == 0;
        }

        public String toString() {
            return "(" + r + ", " + g + ", " + b + ")";
        }
    }

    public boolean canSum(List<Color> colors, Color target) {
        if(colors == null || colors.size() == 0 || target == null) {
            return false;
        }
        return helper(colors, 0, target);
    }

    private boolean helper(List<Color> colors, int index, Color target) {
        if(target.equalsZero()) {
            return true;
        }
        for(int i = index; i < colors.size(); i++) {
            if(target.substract(colors.get(i))) {
                if(helper(colors, i + 1, target)) {
                    return true;
                }
                target.add(colors.get(i));
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ColorSum sample = new ColorSum();
        List<Color> colors = new ArrayList<>();
        colors.add(new Color(86, 5, 211));
        colors.add(new Color(128, 99, 5));
        colors.add(new Color(92, 25, 6));
        colors.add(new Color(16, 45, 4));
        Color target = new Color(236, 169, 15);
        System.out.println(sample.canSum(colors, target));
    }
}